【算法】位运算

1. 位运算符

在C++里，位运算一共有六种：

1. &，按位与。
2. |，按位或。
3. ^，异或符。
4. ~，按位取反符。
5. >>，算术右移运算符，即左侧用符号为补位，比如同样右移四位：0000 1111->0000 0000，而1111 0000->1111 1111。
6. <<，左移运算符。

Java语言在上述基础上，多了一个逻辑右移运算符>>>，即右移时高位只补0。

2. 位运算符的各种用法

1. 判断奇偶

设一个十进制数$N$的补码二进制表示为$a_na_{n-1}\cdots a_1$，则对于正数有：
$$
N = a_n \times 2^{n-1} + a_{n-1}\times 2^{n-2}+\cdots+a_1 \times 1
$$
对于负数有：
$$
N = -a_n \times 2^{n-1} + a_{n-1}\times 2^{n-2}+\cdots+a_1 \times 1
$$

公式参见《深入理解计算机系统》。

对于一个二进制数来说，除去其最低位，各位的权重都为2的整数次幂，修改它们，等价于加上/减去一个偶数，不影响二进制数的奇偶性。

二进制数字的奇偶性由其最低位决定，最低位为1，则该数为奇，否则为偶。

根据上述理论，可写出判断奇偶数的代码:

bool IsOdd(int num) {
    return num & 1;
}

比如Leetcode191. Number of 1 Bits，就是该用法的变体，解法如下：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int result = 0;
        while(n != 0) {
            if(n & 1) result++;
            n >>= 1;
        }
        return result;
    }
};

2. swap()函数的位运算实现

出自《深入理解计算机系统》。一般来说，没人会这么写的，说实话。

至于为什么，看看下面提到的异或的性质。

void swap(int& a, int& b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

3. 异或的性质&只出现一次的数字

只出现一次的数字问题为Leetcode136. Single Number，解法如下：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(int i : nums) {
            result ^= i;
        }
        return result;
    }
};

解这道题，不得不知道异或的性质：

1. 交换律：$a \oplus b = b \oplus a$。
2. 结合律：$a\oplus (b\oplus c) = (a\oplus b)\oplus c$。
3. 无序性：任意多个元素进行异或运算，结果与运算次序无关。
4. $x\oplus x = 0$，$x\oplus 0 = x$。事实上，这是一个幺半群，0是该幺半群的单位元/幺元。

所以，对于上面那道题，由于大多元素出现两次，只有一个元素出现一次，就可以使用第四条性质求解。

此外，对于Leetcode268. Missing Number则有使用异或的解法：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int target = 0;
        for(int i = 0; i <= nums.size(); ++i) {
            target ^= i;
        }
        for(int i : nums) {
            target ^= i;
        }
        return target;
    }
};

4. 乘除法的简化

理论上来讲，若二进制数字有无限位，则左移1位等价于乘2，右移一位等价于除2。

所以乘/除2的整数次幂可以用移位位运算简化：

void Times2(int& a) {
    a <<= 1;
}
void Divide2(int& a) {
    a >>= 2;
}

5. 判断一个正数是否为2的整数幂

这种数的补码表示只有一个1，这种数减一会让1后面的所有0置1,本身置0,即：00100 - 00001 = 00011。其他数字没有这个特点。

bool IsPowOf2(int a) {
	return !(a & (a - 1));
}

比如Leetcode338. Counting Bits：

class Solution {
public:
    vector<int> countBits(int n) {
        int lower_bound = 0;
        vector<int> result;
        for(int i = 0; i <= n; i++) {
            if((i & (i - 1)) == 0) {
                result.push_back(!(i == 0));
                lower_bound = i;
            } else {
                result.push_back(result[i - lower_bound] + 1);
            }
        }
        return result;
    }
};

6. 不用加法运算符实现加法

本题为Leetcode371. Sum of Two Integers。按照半加器的思路来就行。

每次只考虑最后一位，进位由$a\And b$决定，而本位则由$a \oplus b$决定。

解法：

class Solution {
public:
    int getSum(int a, int b) {
        while(b != 0) {
            int carry = a & b;
            a ^= b;
            b = carry << 1;
            if(b == 0 && carry == 0) break;
        }
        return a;
    }
};

7. 位反转

移位运算也可以做一些有用的操作，将二进制数字看作一个数组即可。本题为Leetcode190. Reverse Bits。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for(int i = 0; i < 32; ++i) {
            result <<= 1;
            result += (n & 1);
            n >>= 1;
        }
        return result;
    }
};