一文解决位运算

技法1：减一与

我们先来关注一个特性：

对于数字1111001000，对其减一可得：
1111000111
将两个数字做与运算，可得11110000000
    1111001000
&    1111000111
---------------
    11110000000
我们会发现，经过n = n&(n-1)之后，我们可以将最后的一个1消去

有了这个特性，我们可以解决下面这些题目：

231. 2 的幂

解：2的幂特点就是，1、100、10000、10000000。只有1个“1”。

bool isPowerOfTwo(int n) {
    return (n>0)&&(n&(n-1))==0;
}

342. 4的幂

解：在2的幂基础上，分类讨论。其中\(2^{2x+1}mod3==2\)、\(2^{2x}mod3==1\)

bool isPowerOfFour(int n) {
    return n>0 && (n&(n-1))==0 && (n%3 == 1);
}

191. 位1的个数

解：循环地将最后一个1消去，即可数出1的个数。

461. 汉明距离

解：先取异或，然后统计1的个数。

技法2：异或相消

假设a != b
那么 a ^ b ^ a = b;

136. 只出现一次的数字

进阶（虽然没有用到异或相消原则）

137. 只出现一次的数字 II

统计每个位是否为3的倍数，如果是，则ans的该位数字为1

int ans = 0;
for(int i = 0 ; i < 32; i ++){
    int sum = 0;
    for(auto x : nums){
        sum  += (x >> i)&1;
    }
    ans += sum%3==0? 0 : 1 << i;
}
return ans;

技法3：正负值异或

low = n & (-n);

这样可以获取最低位的1。可以解决下面这样的问题：

260. 只出现一次的数字 III

技法4：数字交换

加减数字交换(可能产生溢出)

a = a + b;
b = a - b;
a = a - b;

异或数字交换

a = a^b;
b = a^b;
a = a^b;

为什么可以呢？我们展开来看看：

a = a^b;
b = a^b = a^b^b = a;
a = a^b = a^b^a = b;

其他

693. 交替位二进制数

解：可以使用3（二进制为11）来循环作与运算

371. 两整数之和

解：使用与来计算进位，使用异或来计算当前为的数字。

面试题 05.01. 插入