常用技巧

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

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

位运算基础问题

汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

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

示例 2：

输入：x = 3, y = 1
输出：1

按位异或，统计 1 的个数即可

代码 
1
2
3
4
5
6
7
8
int hammingDistance(int x, int y) {
    int diff = x ^ y, ans = 0;
    while (diff) {
        ans += diff & 1;
        diff >>= 1;
    }
    return ans;
}

颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

使用算术左移和右移，可以很轻易地实现二进制的翻转。

代码 
1
2
3
4
5
6
7
8
9
uint32_t reverseBits(uint32_t n) {
    uint32_t ans = 0;
    for (int i = 0; i < 32; i++) {
        ans <<= 1;
        ans += n & 1;
        n >>= 1;
    }
    return ans;
}

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

需要用到异或运算的性质：

  • a \^ a = 0
  • a \^ 0 = a
  • a \^ b \^ a = b \^ (a \^ a) = b（交换律和结合律）

所以只要全部异或最后结果就是答案

代码 
1
2
3
4
5
6
int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (const int & num: nums)
        ans ^= num;
    return ans;
}

二进制特性

利用二进制的一些特性，我们可以把位运算使用到更多问题上。例如，我们可以利用二进制和位运算输出一个数组的所有子集。假设我们有一个长度为 n 的数组，我们可以生成长度为 n 的所有二进制，1 表示选取该数字，0 表示不选取。这样我们就获得了 $2^n$ 个子集。

4的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true；否则，返回 false。

首先我们考虑一个数字是不是 2 的（整数）次方：如果一个数字 n 是 2 的整数次方，那么它 的二进制一定是0…010…0 这样的形式；考虑到 n − 1 的二进制是 0…001…1，这两个数求按位与 的结果一定是 0。因此如果 n & (n - 1) 为 0，那么这个数是 2 的次方。如果这个数也是 4 的次方，那二进制表示中 1 的位置必须为奇数位。我们可以把 n 和二进制的 10101…101（即十进制下的 1431655765）做按位与，如果结果不为 0，那么说明这个数是 4 的 次方。

代码 
1
2
3
bool isPowerOfFour(int n) {
    return n > 0 && !(n & (n - 1)) && (n & 1431655765);
}

最大单词长度乘积

给你一个字符串数组 words，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0。

怎样快速判断两个字母串是否含有重复数字呢？可以为每个字母串建立一个长度为 26 的二进制数字，每个位置表示是否存在该字母。如果两个字母串含有重复数字，那它们的二进制表示的按位与不为 0。同时，我们可以建立一个哈希表来存储字母串（在数组的位置）到二进制数字的映射关系，方便查找调用。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProduct(vector<string>& words) {
    unordered_map<int, int> hash;
    int ans = 0;
    for (const string & word : words) {
        int mask = 0, size = word.size();
        for (const char & c : word)
            mask |= 1 << (c - 'a');
        hash[mask] = max(hash[mask], size);
        for (const auto& [h_mask, h_len]: hash) {
            if (!(mask & h_mask))
                ans = max(ans, size * h_len);
        }
    }
    return ans;
}

比特位计数

给定一个非负整数 n，求从 0 到 n 的所有数字的二进制表达中，分别有多少个 1。

本题可以利用动态规划和位运算进行快速的求解。定义一个数组 dp，其中 dp[i] 表示数字 i 的二进制含有 1 的个数。对于第 i 个数字，如果它二进制的最后一位为 1，那么它含有 1 的个数 则为 dp[i-1] + 1；如果它二进制的最后一位为 0，那么它含有 1 的个数和其算术右移结果相同，即 dp[i>>1]。

代码 
1
2
3
4
5
6
7
vector<int> countBits(int num) {
    vector<int> dp(num+1, 0);
    for (int i = 1; i <= num; ++i)
        dp[i] = i & 1? dp[i-1] + 1: dp[i>>1];	
    // 等价于dp[i] = dp[i&(i-1)] + 1;
    return dp;
}

练习

丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2

实际是上面例题的变种，只需在后面加上 0-n 的数字，即可转为只出现一次的数字那一题

代码 
1
2
3
4
5
6
7
8
9
int missingNumber(vector<int>& nums) {
    int res = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++)
        res ^= nums[i];
    for (int i = 0; i <= n; i++)
        res ^= i;
    return res;
}

注意这种巧妙优雅的写法，看似没加，实际等于加了

交替位二进制数

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

对输入 n 的二进制表示右移一位后，得到的数字再与 n 按位异或得到 a。当且仅当输入 n 为交替位二进制数时，a 的二进制表示全为 1（不包括前导 0）。这里进行简单证明：当 a 的每一位为 1 时，当且仅当 n 的所有相邻位相异，即 n 为交替位二进制数。

将 a 与 a + 1 按位与，当且仅当 a 的二进制表示全为 1 时，结果为 0。这里进行简单证明：当且仅当 a 的二进制表示全为 1 时，a + 1 可以进位，并将原最高位置为 0，按位与的结果为 0。否则，不会产生进位，两个最高位都为 1，相与结果不为 0。

代码 
1
2
3
4
bool hasAlternatingBits(int n) {
    long a = n ^ (n >> 1);
    return (a & (a + 1)) == 0;
}

很简单的两条性质，但不容易想到

数字的补数

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

与同位数的最大的取异或

代码 
1
2
3
4
5
6
7
8
int findComplement(int num) {
    long tmp = num, c = 1;
    while (tmp) {
        c <<= 1;
        tmp >>= 1;
    }
    return num ^ (c - 1);
}

只出现一次的数字III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

例题的进阶版，全部异或后剩下 $x_1$ 和 $x_2$ 的异或结果，x 显然不会等于 0，因为如果 x=0，那么说明 $x_1 = x_2$，这样就不是只出现一次的数字了。因此，我们可以使用位运算 x \& -x 取出 x 的二进制表示中最低位那个 1，设其为第 l 位，那么 $x_1$ 和 $x_2$ 中的某一个数的二进制表示的第 l 位为 0，另一个数的二进制表示的第 l 位为 1。

这样一来，我们就可以把 nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。可以发现：

  • 对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
  • 对于任意一个在数组 nums 中只出现了一次的元素，即 $x_1$ 和 $x_2$ 它们会被包含在不同类中。

因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 $x_1$，另一类会得到 $x_2$。这样我们就找出了这两个只出现一次的元素。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> singleNumber(vector<int>& nums) {
    int xorsum = 0;
    for (int num: nums)
        xorsum ^= num;
    // 防止溢出
    int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
    int type1 = 0, type2 = 0;
    for (int num: nums) {
        if (num & lsb)
            type1 ^= num;
        else
            type2 ^= num;
    }
    return {type1, type2};
}