1. 异或运算的定律

异或运算的目的是判断两个数是不是不同。假设a、b、c都是整数,则

  • 零忽略:a^0=a
  • 相同抵消:a^a=0
  • 交换律:a^b=b^a
  • 结合律:a^b^c=a^(b^c)

2. 常见用异或技巧的题目

2.1. 翻转二进制的某些位

做法就是让原来的数与指定位是1其余位是0的数进行异或。

比如二进制11010的第2、3位翻转后变成11100,做法就是

11010^00110

2.2. 直接交换两个整数值

  • 题目:有两个变量int a=y,b=y; 要求交换a和b的值,但不能引入新的变量。
  • 解法:

a=a^b;

b=a^b;//等号右边a^b^b,抵消b剩a

a=a^b;//等号右边a^b^a,抵消a剩b

2.3. 求二进制最右边1

  • 题目:如输入二进制00110101000,输出二进制1000;如输入二进制0010100000,输出二进制100000
  • 解法:n&(~n+1)

假设n是0010100000

n取反后,右边原来的0全部变为1

1101011111

加1会让这些1全部又变成0,直到遇到最右边的第一个0,就停止了,高位还是原来的取反

1101100000

而那个0就是原来的最右边的1。

因为经过(~n+1)变换后最右1的左边是原来的高位取反,右边是0,所以用变换后的数与原来的数做“与运算”,最右1的左边高位都不一样,就全是0了,最右1本身及其右边就保留下来了。

2.4. 出现奇数次的1个数

  • 题目:有一组数,里面只有一个数出现了奇数次,其他数都出现了偶数次,求出现奇数次的数是哪个?
  • 解法:把这些数全部异或起来,出现偶数次的数会抵消掉,剩下的就是要求的数。

2.5. 出现奇数次的2个数

  • 题目:有一组数,里面只有2个不同的数aa和b出现了奇数次,其他数都出现了偶数次,求出现奇数次的数是哪两个?
  • 思路:a和b不一样,a^b就不为0,a和b在某个二进制位上肯定有一个是1(假设是a)另一个是0(假设是b)。在这个特定的二进制位上,不算a,1的个数肯定是偶数个,所以算上a后,1的个数就是奇数个。在这个位上对所有数进行异或,就得到了a。“这个位”我们就取最右边的1
  • 解法:
  1. 把这些数全部异或起来,出现偶数次的数会抵消掉,剩下的就是a^b,记为e。
  2. 求出e的最右1记为c,假设最右1在第4位,c大概长这样子0000001000,说明a和b一定有一个数的第4位是1(假设是a),另一个的第4位是0(假设是b)
  3. 所有与c异或,结果不为0的数,一定不包含b,把它们全部异或到一起,就得到了a
  4. 把a跟e异或到一起,就得到了b

2.6. 二进制1的个数

  • 题目:给一个整数a,求它二进制1的个数,如二进制001011010110的1有6个。
  • 解法:循环a,获取它最右边1【用a&(~a+1)】,假设为c,然后用c异或a(相当于把a最右边的1个1变成0),直到a为0,统计循环次数,就是1的个数。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部