01 位运算基础

​ 位运算是算法题里比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括：“∧” 按位异或、“&” 按位与、“|” 按位或、“∼” 取反、“<<” 算术左移和 “>>” 算术右移。以下是一些常见的位运算特性：

异或	与	或
x ^ 0000 = x	x & 0000 = 0	x | 0000 = x
x ^ 1111 = ~x	x & 1111 = x	x | 1111 = 1111
x ^ x = 0	x & x = x	x | x = x

​ 除此之外， n & (n - 1) 可以去除 n 的位级表示中最低的那一位，例如对于二进制表示 11110100，减去 1 得到 11110011，这两个数按位与得到 11110000。

​ n & (-n) 可以仅保留 n 的位级表示中最低的那一位，例如对于二进制表示 11110100，取负得到 00001100，这两个数按位与得到 00000100。

​ 回顾一下移位操作，移位操作是一种基本操作，是一种直接对二进制数据的位运算操作，移位运算又包含了逻辑移位（logical shift）和算术移位（arithmetic shift）两种。

• 逻辑移位：移出去的位丢弃，空缺位（vacant bit）用 0 填充。
• 算术移位：移出去的位丢弃，空缺位（vacant bit）用“符号位”来填充，所以一般用在右移运算中。

​ 无符号数，不管是左移还是右移都是逻辑移位；有符号数，做左移运算是逻辑移位，而做右移运算是算术移位。

461 汉明距离 (opens new window)

给定两个十进制数字，求它们二进制表示的汉明距离（Hamming distance，即不同位的个数）。

输入是两个十进制整数，输出是一个十进制整数，表示两个输入数字的汉明距离。

输入：x = 1, y = 4 输出：2 解释：1 (0 0 0 1)；4 (0 1 0 0)

解析：

​ 求二进制数不同位的个数，直接使用将俩个数进行按位异或操作，不同位的结果就是 1，所以最终统计异或结果中的 1 的个数即可。

​ 计算二进制数 1 的个数的方法：不断将二进制数算数右移，将其与 1 进行与运算，如果末位是 1 则加入计数。

class Solution {
public:
    int hammingDistance(int x, int y) {
        // 异或运算
        int diff = x^y;
        int ans = 0;
        while(diff){
            // 与运算 判断末位是否为 1
            ans += diff & 1;
            // 算术右移动 将已经被统计的 1 移出
            diff = diff>>1;
        }
        return ans;
    }
};

190 颠倒二进制位 (opens new window)

给定一个十进制整数，输出它在二进制下的翻转结果。

输入和输出都是十进制整数。

输入：n = 00000010100101000001111010011100

输出：964176192 (00111001011110000010100101000000)

解释：将 n 的二进制串倒转

解析：

​ 使用算术左移和右移，可以很轻易地实现二进制的翻转。保存结果的二进制串每次向左移动一位腾出末位，然后将 n 与 1 取出 n 的末位并放入结果腾出的末位，放入之后 n 向右移动一位将已放入的位移出。

​ 一个简单的示例：

	1	2	3	4	5
ans (算术左移)	0000	0000	0001	0010	0101
n (算术右移)	1010	0101	0010	0001	0000

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        // 无符号32位整型
        uint32_t ans = 0;
        for(int i=0;i<32;++i){
            // 每次先将结果左移一位腾出位置
            ans <<= 1;
            // 将 n 当前的最后一位放到上一步ans腾出的位置（末位）
            ans += n&1;
            // 将已经放入结果的位移出
            n >>= 1;
        }
        return ans;
    }
};

693 交替位二进制数 (opens new window)

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现

输入一个整数，输出一个布尔类型表示二进制表示是否总是 0、1 交替出现

输入：n = 10
输出：true
解释：10 的二进制表示是：1010

解析：

​ 一种简单的思路是不断使用算术右移将n的二进制表示末位移出，使用按位与运算获取末位是0还是1，并且比较第 i 个和第 i-1 个末位是否相同，如果相同则直接返回false，检查完成则返回true。

class Solution {
public:
    bool hasAlternatingBits(int n) {
        // 记录第一个末位
        int pre = n & 1;
        n>>=1;
        while(n){
            // 比较第 i 个和第 i-1 个末位
            int now = n & 1;
            if(now == pre){
                return false;
            }else{
                // 更新前一个状态
                pre = now;
            }
            n >>= 1;
        }
        return true;
    }
};