从「只出现一次的数字」到位运算工具箱

写到 LeetCode 136「只出现一次的数字」时，我先后想到了双重循环、排序和哈希表。它们都能找到答案，却不能同时满足题目的两个要求：线性时间复杂度与常量额外空间。看了题解才发现，突破口居然是一直被我忽略的位运算。

这篇文章从这道题出发，把常见位运算技巧整理成一套可以复用的工具箱。重点不只是记住公式，还要弄清楚每个公式为什么成立、适合解决什么问题，以及 C++ 中有哪些容易踩到的边界。

起点：只出现一次的数字

LeetCode 136. 只出现一次的数字给出一个非空整数数组：除一个元素只出现一次外，其余元素都出现两次。题目要求在线性时间内找出这个元素，并且只使用常量额外空间。

常规方案为什么差一点

异或到底做了什么

异或运算符是 ^。对于同一位，两个二进制位不同则结果为 1，相同则结果为 0：

从真值表可以得到三个关键性质：

• x ^ x = 0：相同的数会抵消。
• x ^ 0 = x：0 是异或运算的单位元。
• 异或满足交换律和结合律：元素出现的顺序不会影响最终结果，成对的数隔得再远也能抵消。

以数组 [4, 1, 2, 1, 2] 为例，按遍历顺序计算：

0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4

换一种写法，抵消关系会更清楚：

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

所以只需要一个变量保存累计异或值：

#include <vector>

int singleNumber(const std::vector<int>& nums) {
    int answer = 0;
    for (int value : nums) {
        answer ^= value;
    }
    return answer;
}

即使数组中有负数，两个相同的负数也拥有相同的位表示，异或后仍然会变成全 0，因此这个抵消规律照样成立。

先看懂这组相似题的共同结构

下面五道题都在寻找“正常数据”与“实际数据”之间的差异。关键不是看到题目就机械地异或，而是先判断：把应该成对的内容放在一起后，最后会剩下几个特殊值。

lowbit：只保留最低位的 1

x & -x 通常叫作 lowbit(x)，它只保留 x 最低位的那个 1，其余位全部清零。

例如用 8 位二进制观察十进制数 44：

x       = 0010 1100   (44)
-x      = 1101 0100   (按位取反后加 1)
x & -x  = 0000 0100   (4)

原因在于：求补码相反数时，最低位 1 右边的 0 最终仍是 0，最低位的这个 1 会在“取反再加 1”后重新变成 1，而它左边的位都与原数相反。两者按位与后，只有这个最低位的 1 能留下来。

#include <cstdint>

std::uint32_t lowbit(std::uint32_t x) {
    return x & (0u - x);
}

LeetCode 260：只出现一次的数字 III

这道题把特殊数字从一个增加到了两个：其余数字仍出现两次，但现在有两个数字 p 和 q 只出现一次。全部异或只能得到 p ^ q。因为 p != q，所以 p ^ q 至少有一位是 1；取它的 lowbit，就能找到 p 与 q 必然不同的一位。

接着按这一位是 0 还是 1 把所有数字分成两组。相同数字一定进入同一组并在组内抵消，而 p 和 q 会被分开。

#include <bit>
#include <cstdint>
#include <utility>
#include <vector>

std::pair<std::int32_t, std::int32_t> twoSingleNumbers(
    const std::vector<std::int32_t>& nums) {
    std::uint32_t mixed = 0;
    for (std::int32_t value : nums) {
        mixed ^= static_cast<std::uint32_t>(value);
    }

    const std::uint32_t dividingBit = mixed & (0u - mixed);
    std::uint32_t first = 0;
    std::uint32_t second = 0;

    for (std::int32_t value : nums) {
        const auto bits = static_cast<std::uint32_t>(value);
        if ((bits & dividingBit) == 0) {
            first ^= bits;
        } else {
            second ^= bits;
        }
    }

    return {
        std::bit_cast<std::int32_t>(first),
        std::bit_cast<std::int32_t>(second)
    };
}

以 [1, 2, 1, 3, 2, 5] 为例，全部异或得到 3 ^ 5 = 6，也就是二进制 110。它的 lowbit 是 010，说明 3 和 5 在第 1 位上不同，正好可以据此分组。

lowbit 与树状数组

树状数组用 lowbit(i) 表示节点 i 负责的区间长度。查询前缀和时不断清除最低位的 1，向父区间移动；单点更新时不断加上 lowbit(i)，访问所有包含当前位置的上级区间。

// 查询前缀和：i 逐步变小
for (int i = index; i > 0; i -= i & -i) {
    answer += tree[i];
}

// 单点增加：i 逐步跳到上级区间
for (int i = index; i <= n; i += i & -i) {
    tree[i] += delta;
}

清除最低位的 1：x & (x - 1)

x - 1 会把 x 最低位的 1 变成 0，并把它右边的所有 0 变成 1。再与原数按位与，就会清除最低位的 1，其他更高位保持不变。

x           = 0010 1100   (44)
x - 1       = 0010 1011   (43)
x & (x - 1) = 0010 1000   (40)

统计二进制中 1 的个数

每执行一次 x &= x - 1，就会删除一个 1，因此循环次数正好等于 1 的数量。

int countOnes(std::uint32_t x) {
    int count = 0;
    while (x != 0) {
        x &= x - 1;
        ++count;
    }
    return count;
}

例如 44 = 0010 1100 的变化过程是 44 → 40 → 32 → 0，总共执行 3 次，所以它有 3 个 1。

判断是否为 2 的幂

正的 2 的幂只有一个二进制位是 1。清除这个 1 后结果必然为 0：

bool isPowerOfTwo(std::uint32_t x) {
    return x != 0 && (x & (x - 1)) == 0;
}

不能省略 x != 0，因为 0 也会让后半个表达式得到 0，但 0 不是 2 的幂。

计算汉明距离

两个整数的汉明距离，就是它们有多少个二进制位不同。先异或标出不同的位置，再数 1：

int hammingDistance(std::uint32_t a, std::uint32_t b) {
    return countOnes(a ^ b);
}

用位运算模拟加法

普通二进制加法包含两部分：

• a ^ b：计算每一位“不考虑进位”的和。
• (a & b) << 1：找出两边同时为 1 的位置，并把进位左移一位。

因此有下面这个恒等关系：

a + b = (a ^ b) + ((a & b) << 1)

注意右侧仍然有加法。真正模拟时，要把“无进位的和”与“进位”继续重复计算，直到进位变成 0。

以 13 + 9 为例：

a             = 0 1101   (13)
b             = 0 1001   (9)
a ^ b         = 0 0100   (4)
(a & b) << 1  = 1 0010   (18)

继续计算 4 与 18：
0 0100 ^ 1 0010        = 1 0110   (22)
(0 0100 & 1 0010) << 1 = 0       (没有进位，结束)

std::uint32_t addWithoutPlus(std::uint32_t a, std::uint32_t b) {
    while (b != 0) {
        const std::uint32_t carry = (a & b) << 1;
        a ^= b;
        b = carry;
    }
    return a;
}

状态压缩：用一个整数表示集合

当元素数量很少，每个元素只有“选”或“不选”两种状态时，可以让整数的第 j 位表示第 j 个元素是否被选中。

例如有 A、B、C 三个元素，掩码 101 表示选中 A 和 C，没有选 B。于是，一个 n 位整数就能表示 2^n 个不同子集。

枚举 n 个元素的所有子集

#include <cstdint>

// 前提：0 <= n < 64
const std::uint64_t limit = std::uint64_t{1} << n;
for (std::uint64_t mask = 0; mask < limit; ++mask) {
    for (int j = 0; j < n; ++j) {
        if ((mask >> j) & 1u) {
            // 第 j 个元素被选中
        }
    }
}

外层一共枚举 2^n 个掩码。如果每次还要扫描 n 位，完整复杂度是 O(n · 2^n)。

枚举 mask 的所有非空子集

for (std::uint64_t subset = mask;
     subset != 0;
     subset = (subset - 1) & mask) {
    // subset 是 mask 的一个非空子集
}

subset - 1 产生比当前值小的下一个候选状态，再用 & mask 删除所有不属于原集合的位。以 mask = 1101 为例，枚举顺序是：

1101 → 1100 → 1001 → 1000 → 0101 → 0100 → 0001 → 结束

如果 mask 中有 p 个 1，它有 2^p 个子集，所以这段循环的复杂度是 O(2^popcount(mask))。

枚举每个集合的所有子集

for (std::uint64_t mask = 0; mask < limit; ++mask) {
    for (std::uint64_t subset = mask;
         subset != 0;
         subset = (subset - 1) & mask) {
        // subset 是 mask 的非空子集
    }
}

看起来像两层 2^n，但总复杂度不是 O(4^n)，而是 O(3^n)。对于每一个元素，它只有三种归属：

1. 不在 mask 中；
2. 在 mask 中，但不在 subset 中；
3. 同时在 mask 和 subset 中。

n 个元素各有 3 种选择，因此总状态数是 3^n。

枚举恰好含 k 个 1 的掩码

Gosper's Hack 可以直接跳到“下一个拥有相同 1 的数量”的整数，不需要扫描全部 2^n 个状态。

// 前提：1 <= k <= n < 64
const std::uint64_t limit = std::uint64_t{1} << n;

for (std::uint64_t mask = (std::uint64_t{1} << k) - 1;
     mask < limit; ) {
    // 处理 mask

    const std::uint64_t low = mask & (std::uint64_t{0} - mask);
    const std::uint64_t ripple = mask + low;
    mask = ripple | (((mask ^ ripple) >> 2) / low);
}

当 n = 5、k = 3 时，掩码按下面的顺序出现：

00111, 01011, 01101, 01110, 10011,
10101, 10110, 11001, 11010, 11100

一共恰好有 C(5, 3) = 10 个状态。若 k = 0，唯一结果是空集 0，应单独处理。

拆位：每一位独立统计贡献

很多题看起来在操作整个整数，实际上每一位之间互不影响。通用步骤是：

1. 从低位到高位枚举二进制位；
2. 只统计当前位的 0 和 1；
3. 计算这一位对答案的贡献；
4. 把各位贡献合并成最终答案。

LeetCode 137：只出现一次的数字 II

这道题中，其余数字从出现两次改成了出现三次。此时不能直接全员异或，因为 x ^ x ^ x = x，三个相同数字不会消失。解决方法是把每一位上的 1 分别统计出来，再对 3 取模。

以数组 [2, 2, 2, 5] 为例，2 的二进制是 010，5 是 101。逐位统计 1 的数量：

最后重新拼出 101，也就是 5。出现三次的数在每一位产生的 1 都是 3 的倍数，对 3 取模后会被消掉。

#include <bit>
#include <cstdint>
#include <vector>

std::int32_t singleNumberAmongTriples(
    const std::vector<std::int32_t>& nums) {
    std::uint32_t answer = 0;

    for (int bit = 0; bit < 32; ++bit) {
        int ones = 0;
        for (std::int32_t value : nums) {
            const auto bits = static_cast<std::uint32_t>(value);
            ones += (bits >> bit) & 1u;
        }

        if (ones % 3 != 0) {
            answer |= std::uint32_t{1} << bit;
        }
    }

    return std::bit_cast<std::int32_t>(answer);
}

这里使用无符号数移动和拼接全部 32 位，最后用 C++20 的 std::bit_cast 原样解释这些位，因此也能正确还原负数。

另一个拆位案例：所有数对的异或之和

假设要计算所有无序数对的异或之和。对第 bit 位来说，只有一个数该位为 1、另一个数该位为 0 时，异或结果才会在这一位贡献 2^bit。

若当前位有 ones 个 1、zeros 个 0，就有 ones × zeros 个数对在这一位不同：

#include <cstddef>
#include <vector>

long long sumOfPairwiseXor(const std::vector<int>& nums) {
    long long answer = 0;

    // 这个简单版本假设 nums 中都是非负 int
    for (int bit = 0; bit < 31; ++bit) {
        long long ones = 0;
        for (int value : nums) {
            ones += (value >> bit) & 1;
        }

        const long long zeros =
            static_cast<long long>(nums.size()) - ones;
        answer += ones * zeros * (1LL << bit);
    }
    return answer;
}

例如 [1, 2, 3] 的三个数对为 1 ^ 2 = 3、1 ^ 3 = 2、2 ^ 3 = 1，总和是 6。拆位后，第 0 位贡献 2，第 1 位贡献 4，加起来仍然是 6。

把参照集合一起异或：丢失、增加与错位

LeetCode 136 直接在一个数组内部寻找成对元素。下面三题多了一份“正常数据”作为参照：完整的数字范围、原字符串，或者原本应有的集合。把实际数据与参照数据一起异或，共同部分仍会成对消失。

LeetCode 268：丢失的数字

题目给出 [0, n] 中的 n 个不同数字，其中恰好缺少一个。数组本身提供了实际数字，下标 0 到 n - 1 再加上数组长度 n，正好组成完整范围 [0, n]。

以 nums = [3, 0, 1] 为例，n = 3：

完整范围：0 ^ 1 ^ 2 ^ 3
实际数组：3 ^ 0 ^ 1

全部异或：(0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2 = 2

0、1、3 都出现两次并抵消，唯一没有配对的 2 就是答案。

#include <cstddef>
#include <vector>

int missingNumber(const std::vector<int>& nums) {
    int answer = static_cast<int>(nums.size());

    for (std::size_t i = 0; i < nums.size(); ++i) {
        answer ^= static_cast<int>(i);
        answer ^= nums[i];
    }
    return answer;
}

循环开始前先把 n 放进答案，是因为下标只能自然提供 0 到 n - 1，还缺少完整范围中的最后一个数 n。

LeetCode 389：找不同

题目给出字符串 s，再向其中添加一个字母并打乱顺序得到 t。顺序对异或没有影响，因此把两串的所有字符编码异或起来，相同字符就会成对抵消，只剩新增字符。

s = "abcd"
t = "abcde"

'a' ^ 'b' ^ 'c' ^ 'd'
^ 'a' ^ 'b' ^ 'c' ^ 'd' ^ 'e'
= 'e'

#include <string_view>

char findTheDifference(std::string_view s, std::string_view t) {
    unsigned char answer = 0;

    for (unsigned char ch : s) {
        answer ^= ch;
    }
    for (unsigned char ch : t) {
        answer ^= ch;
    }
    return static_cast<char>(answer);
}

即使 s 中本来就有重复字母也没有关系：t 包含 s 的全部字符，所以每一个原字符在两串合并后都会出现偶数次。

LeetCode 645：错误的集合——位运算法

题目原本应包含 1 到 n，但一个数字被重复写入，导致另一个数字缺失。设重复数字为 D，缺失数字为 M。把实际数组和完整范围 [1, n] 全部异或后，正常数字会抵消，得到：

mixed = D ^ M

这和 LeetCode 260 一样，只知道两个不同数字的异或值。取 lowbit(mixed) 后分组，便能分别还原 D 和 M。但分组结果没有顺序，还要回到原数组检查哪一个出现过两次。

以 [1, 2, 2, 4] 为例，实际数组与 [1, 2, 3, 4] 一起异或后只剩 2 ^ 3 = 1。最低位就是分组位：偶数组最终留下 2，奇数组最终留下 3。扫描原数组后可知 2 是重复值、3 是缺失值。

#include <cstdint>
#include <vector>

std::vector<int> findErrorNumsByXor(
    const std::vector<int>& nums) {
    const auto n = static_cast<std::uint32_t>(nums.size());
    std::uint32_t mixed = 0;

    for (std::uint32_t i = 1; i <= n; ++i) {
        mixed ^= i;
        mixed ^= static_cast<std::uint32_t>(nums[i - 1]);
    }

    const std::uint32_t dividingBit = mixed & (0u - mixed);
    std::uint32_t first = 0;
    std::uint32_t second = 0;

    auto absorb = [&](std::uint32_t value) {
        if ((value & dividingBit) == 0) {
            first ^= value;
        } else {
            second ^= value;
        }
    };

    for (std::uint32_t i = 1; i <= n; ++i) {
        absorb(i);
        absorb(static_cast<std::uint32_t>(nums[i - 1]));
    }

    for (int value : nums) {
        if (value == static_cast<int>(first)) {
            return {static_cast<int>(first),
                    static_cast<int>(second)};
        }
    }
    return {static_cast<int>(second),
            static_cast<int>(first)};
}

这段代码是 O(n) 时间、O(1) 额外空间，但要经历“求异或值、分组、判断身份”三个阶段。位运算法很适合串联 136、260 和 645 的共同思想，不过这道题还有更直接的数学解法。

LeetCode 645：更直接的数学法

仍设重复数字为 D，缺失数字为 M。实际数组与正确集合的元素和之差为：

sumDiff = D - M

平方和之差则是：

squareDiff = D² - M²
           = (D - M)(D + M)

因为 D != M，所以 sumDiff 不会是 0。两式相除可得 D + M = squareDiff / sumDiff，再与 D - M 联立即可求出两个数：

#include <cstddef>
#include <vector>

std::vector<int> findErrorNumsByMath(
    const std::vector<int>& nums) {
    long long sumDiff = 0;     // D - M
    long long squareDiff = 0;  // D² - M²

    for (std::size_t i = 0; i < nums.size(); ++i) {
        const long long actual = nums[i];
        const long long expected = static_cast<long long>(i) + 1;

        sumDiff += actual - expected;
        squareDiff += actual * actual - expected * expected;
    }

    const long long sum = squareDiff / sumDiff;  // D + M
    const long long duplicate = (sumDiff + sum) / 2;
    const long long missing = sum - duplicate;

    return {static_cast<int>(duplicate),
            static_cast<int>(missing)};
}

数学法同样是 O(n) 时间和 O(1) 额外空间，只需一次遍历，推导也更直接。在这道题的取值范围内使用 long long 可以容纳平方和；如果数据范围更大，就必须重新检查乘法与累加是否会溢出。位运算法没有平方和溢出的问题，但步骤更多。这里的“更好”主要是指代码与推导更简洁，并不意味着所有场景都应无条件选数学法。

基础位操作组合

下面假设 x 是无符号整数，并且位编号 k 从 0 开始。对 32 位整数，必须保证 0 <= k < 32。

x & 1 很适合表达“只关心最低位”，但不必把它当成对 x % 2 的性能优化。现代编译器通常能很好地优化这种简单运算，应优先选择最能表达意图的写法。

异或交换的陷阱

下面三行确实可以在两个变量之间交换位模式：

a ^= b;
b ^= a;
a ^= b;

但是，如果 a 和 b 实际引用同一个对象，第一行就会执行 x ^= x，立刻把它清成 0。现代代码直接使用 std::swap(a, b) 更清楚，也不会因为同地址而损坏数据；异或交换更适合作为理解异或性质的小实验，而不是生产代码技巧。

ASCII 英文字母大小写转换

在 ASCII 编码中，同一个英文字母的大写与小写只相差第 5 位，也就是十进制 32：

'A' = 0100 0001   (65)
'a' = 0110 0001   (97)
' ' = 0010 0000   (32)
'_' = 0101 1111   (95)

因此可以得到这些小技巧：

('A' | ' ') == 'a';   // 大写转小写
('b' & '_') == 'B';   // 小写转大写
('d' ^ ' ') == 'D';   // 大小写互相切换

这里要特别注意方向：与空格按位或是大写转小写，与下划线按位与是小写转大写。

区间异或：异或前缀和

异或也能像加法一样建立前缀数组。令 prefix[i] 表示前 i 个元素的异或值：

#include <cstddef>
#include <vector>

std::vector<int> buildXorPrefix(const std::vector<int>& nums) {
    std::vector<int> prefix(nums.size() + 1, 0);
    for (std::size_t i = 0; i < nums.size(); ++i) {
        prefix[i + 1] = prefix[i] ^ nums[i];
    }
    return prefix;
}

int rangeXor(const std::vector<int>& prefix,
             std::size_t left,
             std::size_t right) {
    return prefix[right + 1] ^ prefix[left];
}

因为区间左侧的前缀会出现两次并自行抵消，所以闭区间 [left, right] 的异或值是 prefix[right + 1] ^ prefix[left]。

例如数组 [3, 8, 2, 6] 的前缀异或是 [0, 3, 11, 9, 15]。查询下标 [1, 3] 时，结果为 15 ^ 3 = 12，与直接计算 8 ^ 2 ^ 6 = 12 一致。

看到什么特征，就想到什么工具

C++ 位运算检查清单

1. 先写清位宽。使用 std::uint32_t、std::uint64_t 比依赖 int 的具体宽度更明确。
2. 优先在无符号数上移位。有符号溢出、负数左移以及超范围移位都容易产生未定义行为。
3. 移位量必须小于类型位宽。例如 64 位掩码要求 0 <= k < 64，不能计算 1ULL << 64。
4. 别忘记 0。lowbit(0) = 0；判断 2 的幂时必须显式排除 0；Gosper's Hack 中 k = 0 要单独处理。
5. 把技巧和可读性分开。位运算适合表示位级意图，但不要为了“看起来更快”替换清晰的普通运算。

总结

LeetCode 136 最值得记住的不是一行 answer ^= value，而是它展示的思考方式：当题目描述中出现“成对抵消”“每一位独立”“选或不选”“只保留某个 1”这些信号时，不妨先把十进制整数拆成二进制位再观察。

异或负责抵消，lowbit 负责定位最低位的 1，x & (x - 1) 负责删除最低位的 1，bitmask 负责压缩集合状态，拆位统计负责累积每一位的贡献。把这些操作和具体题型联系起来，位运算就不再是一堆难背的公式，而会逐渐变成一套自然的算法工具。