位运算加法#

位运算加法是指仅仅使用位运算符来实现加法操作，实现位运算加法只需要使用按位与、按位异或和位移运算符。 类似十进制的加法，我们可以将两个数相加分为两步：

1. 计算进位：使用按位与运算符&，然后将结果左移一位。
2. 计算和：使用按位异或运算符^，数学符号表示为$\oplus$

即

换个角度看，$a \oplus b$ 与 $(a\ \&\ b) << 1 = 2(a\ \&\ b)$相加就相当于是新的两个数相加，因此我们把两数相加转换成了新的两个数相加。不过，由于新的加数 $(a \ \&\ b) << 1$ 是由进位得来的，而进位是有限的，所以我们只需要不断地进行这个过程，直到进位为0为止即可完成等价转换，从而完成计算。

int add(int a, int b) {
    while (b != 0) {
        int carry = a & b; // 计算进位
        a = a ^ b; // 计算和
        b = carry << 1; // 将进位左移一位
    }
    return a;
}

Example Problem 最靓数

定义一个数$B$为集合$A = \{A_i\}_{i=1}^N$的最靓数，如果它满足对于集合$A$中的所有数，有$A_i \oplus B = A_i + B$，则称$B$为集合$A$的最靓数。现在请找到对于给定的集合$A$，它的最小正数最靓数$B$。

分析： 将加法拆开，得

即有

说明只要找到对于集合$A$中所有数按位与均为0数即为最靓数。

#include <iostream>

int main() {
    int N;
    scanf("%d", &N);
    int pos = 0;
    int mask = 0;   // mask用于记录查看对于所有的数Ai, 是否某位上有数是有1存在的
    for (int i = 0; i < N; i++) {
        int Ai;
        scanf("%d", &Ai);
        mask |= Ai; // 计算按位或
    }

    while (mask) {
        mask >>= 1; // 右移一位
        pos++; // 计算二进制位数
    }
    int ans = 1 << pos; // 计算最靓数
    printf("%d\n", ans);
    return 0;
}

位运算除法#

位运算除法是指使用位运算来模拟除法操作，主要利用左移（<<）和减法。其核心思想类似于二进制的竖式除法。我们可以通过不断将除数左移，来快速逼近被除数，从而加速计算过程。

例如，要计算 dividend / divisor，我们可以找到最大的 k 使得 divisor << k <= dividend。这意味着结果中包含 1 << k。然后，我们将 dividend 减去 divisor << k，并对余下的部分重复此过程，直到 dividend < divisor。

为了处理负数，我们可以先将被除数和除数都转换为正数，并记录下最终结果的符号。需要特别注意整数溢出的边界情况，尤其是当被除数为 INT_MIN 时。

Example Problem Leetcode 29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

分析： 根据上述原理，我们可以将被除数和除数都转为负数（或正数）进行计算，这样可以避免 INT_MIN 转为正数时溢出的问题。这里我们选择转为负数。

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        
        long dvd = labs(dividend), dvs = labs(divisor), ans = 0;
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
        
        while (dvd >= dvs) {
            long temp = dvs, m = 1;
            while (temp << 1 <= dvd) {
                temp <<= 1;
                m <<= 1;
            }
            dvd -= temp;
            ans += m;
        }
        
        return sign * ans;
    }
};

枚举子集#

位运算是用来枚举子集的强大工具。对于一个包含 n 个元素的集合，总共有 $2^n$ 个子集。我们可以用一个 n 位的二进制数来表示一个子集，其中第 i 位为 1 表示集合中第 i 个元素被选中，为 0 则表示未被选中。

通过从 0（二进制 00...0）到 $2^n - 1$（二进制 11...1）进行遍历，我们就可以生成所有可能的子集。

Example Problem Leetcode 78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

分析： 数组 nums 的长度为 n。我们可以遍历从 0 到 $2^n - 1$ 的所有整数 i。对于每个 i，我们检查它的二进制表示。如果 i 的第 j 位是 1，我们就将 nums[j] 添加到当前子集中。

#include <vector>
#include <cmath>

class Solution {
public:
    std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
        int n = nums.size();
        int num_subsets = 1 << n; // 2^n
        std::vector<std::vector<int>> result;

        for (int i = 0; i < num_subsets; ++i) {
            std::vector<int> subset;
            for (int j = 0; j < n; ++j) {
                // 检查 i 的第 j 位是否为 1
                if ((i >> j) & 1) {
                    subset.push_back(nums[j]);
                }
            }
            result.push_back(subset);
        }
        return result;
    }
};

Example Problem Leetcode 90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。

分析： 当存在重复元素时，直接使用位运算枚举会导致重复子集。例如，对于 [1, 2, 2]，{1, 2} 会被生成两次。为了解决这个问题，我们可以先对数组排序。然后，在枚举时增加一个约束：如果 nums[j] 与 nums[j-1] 相同，并且 nums[j-1] 未被选择（即 i 的第 j-1 位为 0），那么我们跳过 nums[j]。这确保了对于重复元素，我们只在它们的前一个重复元素被选中的情况下才考虑当前元素，从而避免了重复。

#include <vector>
#include <cmath>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        int num_subsets = 1 << n;
        std::vector<std::vector<int>> result;

        for (int i = 0; i < num_subsets; ++i) {
            std::vector<int> subset;
            bool skip = false;
            for (int j = 0; j < n; ++j) {
                // 检查 i 的第 j 位是否为 1
                if ((i >> j) & 1) {
                    // 如果当前元素和前一个元素相同，但前一个元素未被选择，则跳过
                    if (j > 0 && nums[j] == nums[j - 1] && !((i >> (j - 1)) & 1)) {
                        skip = true;
                        break;
                    }
                    subset.push_back(nums[j]);
                }
            }
            if (!skip) {
                result.push_back(subset);
            }
        }
        return result;
    }
};

按位与和公共前缀#

当计算一个连续范围 [left, right] 内所有数字的按位与时，结果实际上是这个范围内所有数字二进制表示的“公共前缀”。任何在 left 和 right 的二进制表示中不同的位，在范围内的某个数字中都会经历从 0 到 1 或从 1 到 0 的变化，这导致按位与操作后该位变为 0。因此，我们只需要找到 left 和 right 的二进制公共前缀。

一个简单的方法是不断将 left 和 right 右移，直到它们相等。此时得到的值就是它们的公共前缀。记录下右移的次数，然后将结果左移相同的次数，即可得到最终答案。

Example Problem Leetcode 201. 数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、 right 端点）。

分析： 如上所述，我们寻找 left 和 right 的二进制公共前缀。通过不断右移 left 和 right 直到它们相等，我们就能找到这个前缀。

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        // 找到 left 和 right 的公共前缀
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        // 将公共前缀左移，得到结果
        return left << shift;
    }
};

按位统计汉明距离#

汉明距离是指两个等长字符串（或二进制数）之间对应位置上不同字符（或位）的数量。要计算一个数组中所有数对的汉明距离总和，逐对比较的效率很低。

一个更高效的方法是按位独立计算。对于整数的每一个二进制位（例如，从第 0 位到第 31 位），我们统计数组中有多少个数在该位上是 1（记为 k），以及多少个数是 0（记为 n-k，其中 n 是数组长度）。在这一位上，k 个 1 和 n-k 个 0 之间可以组成 k * (n-k) 个数对，它们在这一位上的值不同。因此，这一位对汉明距离总和的贡献就是 k * (n-k)。将所有位的贡献相加，即可得到最终结果。

Example Problem Leetcode 477. 汉明距离总和

给定一个整数数组 nums，计算并返回 nums 中所有元素之间汉明距离的总和。

分析： 我们遍历从 0 到 31 的每一位。对于每一位 i，我们统计 nums 中所有数字在该位上为 1 的数量 count。然后，根据公式 count * (n - count) 计算该位对总距离的贡献，并累加到最终结果中。

#include <vector>

class Solution {
public:
    int totalHammingDistance(std::vector<int>& nums) {
        int n = nums.size();
        int total_distance = 0;
        for (int i = 0; i < 32; ++i) {
            int count = 0;
            for (int num : nums) {
                if ((num >> i) & 1) {
                    count++;
                }
            }
            total_distance += count * (n - count);
        }
        return total_distance;
    }
};

状态压缩动态规划#

状态压缩（State Compression）是一种利用位运算来表示和处理状态的动态规划技巧，常用于解决组合优化问题，特别是当状态的维度较小（通常不超过 20）时。我们可以用一个整数的二进制位来紧凑地表示一个集合或一个排列的状态。

Example Problem Leetcode 1494. 并行课程 II

给你一个整数 n 表示某所大学的课程数，从 1 到 n ，以及一个数组 dependencies ，其中 dependencies[i] = [xi, yi] 表示课程 xi 必须在课程 yi 之前完成。同时给你一个整数 k。在一个学期中，你 最多 可以同时修 k 门课程。请你返回完成所有课程所需要的 最少 学期数。

分析： 这是一个典型的状态压缩 DP 问题。我们可以用一个 n 位的二进制数 mask 来表示课程的完成状态，dp[mask] 表示完成 mask 所代表的课程集合所需的最少学期数。

1. 状态定义：dp[mask] 是完成 mask 状态所需的最少学期数。
2. 预处理：prereq[i] 是一个位掩码，表示课程 i 的所有先修课程。
3. 状态转移：从当前状态 mask，我们找出所有可以上的课（即先修课都已完成）。在这些可选课程中，我们选择不超过 k 门来上，形成下一个状态 next_mask。状态转移方程为 dp[next_mask] = min(dp[next_mask], dp[mask] + 1)。
4. 优化：为了避免重复计算组合，我们只考虑可选课程的子集进行转移。

#include <vector>
#include <algorithm>

class Solution {
public:
    int minNumberOfSemesters(int n, std::vector<std::vector<int>>& dependencies, int k) {
        std::vector<int> prereq(n, 0);
        for (const auto& dep : dependencies) {
            prereq[dep[1] - 1] |= 1 << (dep[0] - 1);
        }

        std::vector<int> dp(1 << n, n + 1);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); ++mask) {
            if (dp[mask] > n) continue;

            int can_take = 0;
            for (int i = 0; i < n; ++i) {
                // 如果课程 i 未上过，并且其先修课都已完成
                if (!((mask >> i) & 1) && (mask & prereq[i]) == prereq[i]) {
                    can_take |= 1 << i;
                }
            }

            // 枚举 can_take 的所有子集
            for (int submask = can_take; submask > 0; submask = (submask - 1) & can_take) {
                if (__builtin_popcount(submask) <= k) {
                    int next_mask = mask | submask;
                    dp[next_mask] = std::min(dp[next_mask], dp[mask] + 1);
                }
            }
        }

        return dp[(1 << n) - 1];
    }
};