C++ 位运算技巧与常见算法题解

消除一个数二进制最低位 1

class Solution {
public:
    int hammingWeight(int n) {
        int ans = 0;
        while (n) { 
            n &= n - 1; 
            ans++;
        }
        return ans;
    }
};

2. 比特位计数

题目： [LCR 003. 比特位计数]

题目描述：

给定一个非负整数 n，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1：

• 输入：n = 2
• 输出：[0, 1, 1]
• 解释：0 --> 0；1 --> 1；2 --> 10

示例 2：

• 输入：n = 5
• 输出：[0, 1, 1, 2, 1, 2]
• 解释：0 --> 0；1 --> 1；2 --> 10；3 --> 11；4 --> 100；5 --> 101

说明：

• 0 <= n <= 10^5

解题思路

这道题要每个数的位 1 的个数进行统计，很容易想到对每个数进行位运算，统计出每个数二进制表示的 1 的个数。

代码实现

class Solution {
public:
    int hammingWeight(int n) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            if ((n >> i) & 1) ans++;
        }
        return ans;
    }
    vector<int> countBits(int n) {
        vector<int> ret(n + 1);
        for (int i = 1; i <= n; ++i) ret[i] = hammingWeight(i);
        return ret;
    }
};

这种解法的时间复杂度是 O(32n)，但其实这道题还能用动态规划来做。

dp[i]：表示数字 i 二进制表示中 1 的个数

如果 i 是偶数，其二进制表示中最低位为 0，右移一位后二进制 1 的个数不变，则有 dp[i] = dp[i >> 1]

如果 i 是奇数，其二进制表示中最低位为 1，右移一位后二进制 1 的个数减少了一个，则有 dp[i] = dp[i >> 1] + 1

综上可得

• 递推公式：dp[i] = dp[i >> 1] + (i & 1)

代码实现

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ret(n + 1);
        for (int i = 0; i <= n; ++i) ret[i] = ret[i >> 1] + (i & 1);
        return ret;
    }
};

动态规划的解法时间复杂度严格为 O(n)。

3. 汉明距离

题目： [461. 汉明距离]

题目描述：

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

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

示例 1：

• 输入：2
• 输出：2

示例 2：

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

提示：

• 0 <= x, y <= 2^31 - 1

解题思路

将输入的 x 和 y 右移，逐位比较，统计对应二进制位不同的位置的数目，当 x | y 为 0 时，说明两个数最高位 1 统计完，结束循环。

代码实现

class Solution {
public:
    int hammingDistance(int x, int y) {
        int ans = 0;
        while (x | y) {
            int a = x & 1, b = y & 1; 
            ans += a ^ b; 
            x >>= 1; 
            y >>= 1;
        }
        return ans;
    }
};

这道题还可以用 lowbit 来求解，lowbit 可以提取一个数二进制表示最右侧的 1。

我们可以先将 x 和 y 异或起来，再统计异或结果中 1 的个数。

class Solution {
public:
    int lowbit(int x) {
        return x & -x;
    }
    int hammingDistance(int x, int y) {
        int ret = 0;
        for (int i = x ^ y; i > 0; i -= lowbit(i)) ret++;
        return ret;
    }
};

4. 只出现一次的数字

题目： [136. 只出现一次的数字]

题目描述：

给定一个整数数组 nums，其中元素出现的次数可以是 2 或 1，请你找出只出现一次的元素。

你必须实现一个线性时间复杂度的算法，并且不使用额外空间。

示例 1：

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

示例 2：

• 输入：nums = [4, 1, 2, 1, 2]
• 输出：4

示例 3：

• 输入：nums = [1]
• 输出：1

提示：

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

解题思路

对这道题，我们可以使用哈希表来统计数字出现的次数，然后遍历一次哈希表找出出现次数为 1 的数字。

当然这道题更优的解法是使用异或运算，直接将所有的数异或起来就能得到出现次数为 1 的数字。

代码实现

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

5. 只出现一次的数字 III

题目： [260. 只出现一次的数字 III]

题目描述：

给定一个整数数组 nums，其中有两个元素只出现一次，其余元素都出现两次。请你找出那两个只出现一次的元素并返回。

你可以不使用额外空间，并且要求时间复杂度为 O(n)。

示例 1：

• 输入：nums = [1, 2, 1, 3, 2, 5]
• 输出：[3, 5]
• 解释：[5, 3] 也是有效的答案。

示例 2：

• 输入：nums = [-1, 0]
• 输出：[-1, 0]

示例 3：

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

提示：

• 2 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

解题思路

这道题是 只出现一次的数字 的升级版，要求找到两个只出现一次的元素，我们用异或 + 分治的思路去解决。

1. 将数组的所有数字异或起来，得到两个只出现一次的数字的异或值。
2. 通过位运算得该异或值二进制表示最低位的 1 是第 i 位。
3. 通过第 i 位上值的不同，将原数组划分，因为异或结果二进制表示位为 1 表示只出现一次的两个数字 a 和 b 该比特位的不同，我们只需要根据这个划分依据分别将对应的数字异或起来就能得到只出现一次的两个数字。

原理：异或运算，相同为 0，不同为 1。

代码实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x = 0; // a ^ b = x
        for (auto e : nums) x ^= e;
        // 判断 x 第几位是 1
        int i = 0;
        for (i = 0; i < 32; ++i)
            if ((x >> i) & 1) break;
        // 根据第 i 位划分原数组
        int a = 0, b = 0;
        for (auto e : nums) {
            if ((e >> i) & 1) a ^= e;
            else b ^= e;
        }
        return {a, b};
    }
};

6. 只出现一次的数字 II

题目： [137. 只出现一次的数字 II]

题目描述：

给定一个整数数组 nums，其中每个元素出现三次，除了一个元素只出现一次。请你找出那个只出现一次的元素。

你必须实现一个线性时间复杂度的算法，并且不使用额外空间。

示例 1：

• nums = [2, 2, 3, 2]
• 输出：3

示例 2：

• 输入：nums = [0, 1, 0, 1, 0, 1, 99]
• 输出：99

提示：

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次。

解题思路

题目要求我们找出只出现一次的元素，并且其他元素出现了 3 次。

既然这样，那么我们将每个数对应的比特位上的值加起来，将结果 % 3，得到余数只有 0 和 1（目标元素出现 1 次，其他元素出现 3 次），余数为 0 说明目标元素对应比特位上的值为 0，余数为 1 说明目标元素对应比特位上的值为 1。

这样我们只需要对数组所有元素的 32 个比特位进行同样的操作，就能一位一位的还原出只出现一次的元素。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        for (int i = 0; i < 32; ++i) {
            int bitSum = 0;
            for (auto e : nums) bitSum += (e >> i) & 1;
            x |= (bitSum % 3) << i;
        }
        return x;
    }
};

7. 判定字符是否唯一

题目： [面试题 01.01. 判定字符是否唯一]

题目描述：

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

• 输入：s = "leetcode"
• 输出：false

示例 2：

• 输入：s = "abc"
• 输出：true

提示：

• 0 <= len(s) <= 100
• s[i] 仅包含小写字母
• 如果不使用额外的数据结构，会很加分。

解题思路

一个整型变量有 32 位，而 s[i] 仅包含小写字母，小写字母共有 26 位，所以我们可以利用位图来充当哈希表，快速判断出判定字符是否唯一。

值得注意的是，如果字符串长度大于 26，那说明字符串里一定有重复的字符，直接返回 false。

代码实现

class Solution {
public:
    bool isUnique(string astr) {
        // 当字符串长度大于 26，必定有重复字符
        if (astr.size() > 26) return false;
        // 利用位图做哈希表
        int bitMap = 0;
        for (auto ch : astr) {
            int i = ch - 'a';
            // 判断字符是否已经存在
            if ((bitMap >> i) & 1) return false;
            // 加入哈希表
            bitMap |= 1 << i;
        }
        return true;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)，仅仅使用一个 int 的额外空间。

8. 丢失的数字

题目： [268. 丢失的数字]

题目描述：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• nums 中的所有数字都独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题？

解题思路

对于这道题，我们可以用异或的解决。对不缺失数字的序列 [0, n]，将其全部数异或起来，得到一个异或值，再用这个异或值与缺失数字的数组 nums 的每个元素异或，最后得到的结果就是缺失的数字，因为重复的数字已经被消除掉了 (x ⊕ x = 0)，类比于 136. 只出现一次的数字。

再或者我们可以利用高斯公式快速求出不缺失数字的序列 [0, n] 的所有元素和，再减去缺失数字的数组 nums 的每个元素，最后得到的结果也是缺失的数字。

这道题利用哈希也能解决，不过空间复杂度是 O(n)，相比之下，并不是最优解法。

代码实现

异或

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

高斯求和

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        // 高斯公式求和
        int sum = n * (n + 1) / 2;
        for (auto e : nums) sum -= e;
        return sum;
    }
};

哈希

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int* hash = new int[n + 1]{0};
        for (auto e : nums) hash[e]++;
        for (int i = 0; i <= n; ++i) {
            if (hash[i] == 0) {
                delete[] hash;
                return i;
            }
        }
        return -1;
    }
};

注意：C++ 不支持可变长数组 arr[n]，所以创建哈希表要使用动态开辟的方法，同时记得要进行初始化。

9. 两整数之和

题目： [371. 两整数之和]

题目描述：

给你两个整数 a 和 b，不使用运算符 + 和 -，计算并返回两整数之和。

示例 1：

• 输入：a = 1, b = 2
• 输出：3

示例 2：

• 输入：a = 2, b = 3
• 输出：5

提示：

• -1000 <= a, b <= 1000

解题思路

异或的本质其实是无进位相加，a ⊕ b 得到的是 a 和 b 无进位相加的结果。

而 a 和 b 的进位是 (a & b) << 1，将其左移是因为相加时是进位的 1 是加在当前位的下一位。

所以可以得出两整数之和 sum = a + b ⇒ a ⊕ b + (a & b) << 1

代码实现

迭代写法

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            int x = a ^ b;
            b = (a & b) << 1;
            a = x;
        }
        return a;
    }
};

递归写法

class Solution {
public:
    int getSum(int a, int b) {
        return b == 0 ? a : getSum(a ^ b, (a & b) << 1);
    }
};

提多几句，实际上关于进位的处理实际上是有点问题的，因为 b 是带符号整数，左移操作时如果超出表示范围（左移相当于乘 2），其结果是未定义的，所以进位我们最好用无符号整数类型 unsigned int 来存储，因为无符号整数超出表示范围会自动取模。

10. 消失的两个数字

题目： [面试题 17.19. 消失的两个数字]

题目描述：

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？ 以任意顺序返回这两个数字均可。

示例 1：

• 输入：[1]
• 输出：[2, 3]

示例 2：

• 输入：[2, 3]
• 输出：[1, 4]

提示：

• nums.length <= 30000

解题思路

这道题其实就是缝合了 268. 丢失的数字 和 260. 只出现一次的数字 III，我们还是使用异或 + 分治来解决问题。

1. 异或 [1, n] 和数组 nums 的所有元素，得到异或值 x。
2. 异或结果二进制表示位为 1 表示缺失的两个数字 a 和 b 该比特位的不同，找出异或值二进制表示最低位的 1 是第 i 位。
3. 通过第 i 位上值的不同，将 [1, n] 和数组 nums 的所有元素划分，我们只需要根据这个划分依据分别将对应的元素异或起来就能得到缺失的两个数字。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 求出缺失两个数的异或 x
        int n = nums.size(), x = 0;
        for (int i = 1; i <= n + 2; ++i) x ^= i;
        for (auto e : nums) x ^= e;
        // 2. 找出 a b 二进制中不同的那位 diff
        int diff = 0;
        while (((x >> diff) & 1) == 0) diff++;
        // 3. 根据 diff 位的不同，将所有的数划分为两类并异或
        int a = 0, b = 0;
        for (auto e : nums)
            if ((e >> diff) & 1) a ^= e;
            else b ^= e;
        for (int j = 1; j <= n + 2; ++j)
            if ((j >> diff) & 1) a ^= j;
            else b ^= j;
        return {a, b};
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)