数据结构与算法学习(一)——异或运算的性质与应用

1. 异或的理解

我们通常把异或定义为不同为1,相同为0,即如如下真值表所显示:

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

但从另外一方面想,我们可以将异或运算认为是二进制的无进位相加:

设 a = 10110101

​ b = 01011101

则 a ^ b = 11101000

相当于每位各自相加但是没有进位。

2. 异或的运算性质

  1. 0 ^ N = N N ^ N = 0

  2. a ^ b = b ^ a (交换律) a ^ b ^ c = a ^ (b ^ c) (结合律)

  3. 同样的一组数异或得到的数一定相同,因为不论这组数怎样调换顺序、组合,经过2中的交换率和结合律都可以得到相同顺序的一组数。

3. 异或的应用

3.1 用于交换两个数的变量值


int a = 甲;  //假设a的值为甲,b的值为乙

int b = 乙;

/*下面的程序用于交换两个数的值*/

a = a ^ b;

b = a ^ b;

a = a ^ b;

就这样,a和b的值就已经进行了交换,是不是有点不可思议!😄

下面我们来具体分析一下三步运算中a和b的值:

  • a = a ^ b; a = 甲 ^ 乙 b = 乙

  • b = a ^ b; a = 甲 ^ 乙 b = 乙 ^ 甲 ^ 乙 = 甲 ^ (乙 ^ 乙) = 甲

  • a = a ^ b; a = 甲 ^ 乙 ^ 甲 = (甲 ^ 甲) ^ 乙 = 乙 b = 甲

是不是清楚了很多呢?有没有觉得这种方法很神奇?😁

但这种方法也有一定的限制😥,使用时一定要注意这两个变量是否指向一个内存地址!!!(应用到数组中就是数组下标是否相同),如果两个变量指向一个内存地址,那么异或操作会将变量的值置为0。

3.2 用于解决奇次数问题

  1. 一个数组中,一种数出现了奇数次,其他数出现了偶数次,如何找出这个出现奇数次的数?

分析:经过上面的分析,很容易就想到了用异或的方法,因为只有一个奇数次数,其它都是偶数次数,如果将数组中所有数进行异或操作,那么最后剩下的那个数便是我们所求的奇数次数。

解决:定义一个初值为0的变量,分别与数组中的每个数异或,最后这个变量中保存的值就是所求的奇数次数。

  1. 一个数组中,两种数出现奇数次,其他数出现偶数次,如何求出这两个出现奇数次的数?

分析:😶这下有两个奇数次数了,该怎么办呢?不慌,让我们看看这组数异或后的结果是什么。

显然,这组数异或最后就剩这两个奇数次数了。设这两个数分别为a和b。则异或的最后结果为a ^ b。因为是两种数,所以a != b,则a ^ b != 0,即a和b至少有一个位上是不同的,a ^ b至少在某一位上为1,由a ^ b的结果可以求得这个位。将该数组分成两种,一种是该位上为1的,另一种是该位上不为1的,则a和b分别位于两种数组中。取一个eor',令其该位置为1其他位置为0,用eor'异或数组中所有该位上为1的数,则最后结果一定为a或b。再将a或b与之前所求的a ^ b在进行异或操作,就可以求出另外一个数。至此,a和b都已求出。

有没有觉得异或运算很神奇呢?😁

本人系菜鸟一枚,所写文章皆为学习总结,大佬请轻喷:😱

谢谢阅读:😘,欢迎补充!

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,421评论 0 2
  • 国家电网公司企业标准(Q/GDW)- 面向对象的用电信息数据交换协议 - 报批稿:20170802 前言: 排版 ...
    庭说阅读 11,185评论 6 13
  • 1、用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。 2、用C语言实现函数void ...
    希崽家的小哲阅读 6,355评论 0 12
  • 第一章数和数的运算 一概念 (一)整数 1整数的意义 自然数和0都是整数。 2自然数 我们在数物体的时候,用来表示...
    meychang阅读 2,656评论 0 5
  • 所思——杜甫 苦忆荆州醉司马,谪官樽酒定常开。 九江日落醒何处,一柱观头眠几回。 可怜怀抱向人尽,欲问平安无使来。...
    闲斋若比邻阅读 135评论 0 3