位运算总结

与运算

判断某一位是否为1

需要判断某个数字的第$i^{th}$位是否为1, 使用只有第$i^{th}$位为1的掩码, 与该数字相与, 如果结果不为0, 则该位置为1.

得到掩码的方法是将1左移$i-1$次.

相关题目:

• [191][简单] 位1的个数

将数字的最后一个1位反转为0

对于任意数字$n$, 将$n$与$n-1$相与, 就可以把数字$n$的最后一位变为0.

相关题目:

• [191][简单] 位1的个数

异或运算

1. 异或运算满足结合律.

2. 相同的数字进行异或, 得到的结果为0; 相同的三个数字进行异或, 得到的原来的数字

   题目: [268][简单] 缺失数字

求和

两数求和

对于两个数字a和b, 有:

• a^b: 每位的异或运算, 得到的结果为无进位相加的结果

• a&b: 每位的与运算, 得到的结果为进位结果

因此将这a^b与a&b左移一位相加, 得到的仍然是a+b. 左移一位的目的是实现进位.

参考:

• [67][简单] 二进制求和

• [剑指Offer-65][简单] 不用加减乘除做加法

找数组中的异常数字

在反复出现数字组成的数组中, 找到其中异常的数字, 即独立出现, 或出现次数异常的数字.

• [136][简单] 只出现一次的数字
• [137][中等] 只出现一次的数字 II
• [260][中等] 只出现一次的数字 III