二进制与位运算基础
本节目标
把整数看成固定位宽的位序列，掌握取位、移位、清位、异或消去和位递推。
位运算不是一组需要死记的符号，而是直接处理整数二进制表示的工具。遇到“每一位独立贡献”“成对抵消”“只保留一个有效位”或“按位构造答案”时，先把数看成从低位到高位排列的位序列，再明确题目要求的位宽。
二进制表示
十进制整数可以写成若干个 0 和 1 的和：从右到左，第 k 位的权重是 2^k。例如 13 = 1101₂，最低位是最右侧的 1。处理第 k 位时，要先统一约定：最低位编号为 0，向左依次递增。
正数的二进制表示只有有限个有效位；但题目若规定 32 位，就要把高位补 0 后再理解它。这个约定决定了移位、反转和输出是否保留前导 0。
常用位操作
对单个二进制位，三种基本操作的结果如下：
| a | b | a & b | a | b | a ^ b |
| --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
n & 1只保留最低位，因此可判断n的最低位是 0 还是 1；例如13 & 1 = 1。n >> 1让各位向低位移动一格；对非负整数，13 >> 1 = 6，相当于去掉最低位。n & (n - 1)会清除n的最低位1；例如12 = 1100₂，12 & 11 = 1000₂。它只适用于希望逐个删除有效1的场景，先确认n是否为正数。
异或的三条性质
异或适合表达“相同的项抵消”。它有三条最常用的性质：
- 交换律：
a ^ b = b ^ a，因此可以调整配对顺序。 - 结合律：
(a ^ b) ^ c = a ^ (b ^ c)，因此可以在一次遍历中累计。 - 自反消去：
a ^ a = 0，并且a ^ 0 = a，所以偶数次出现的相同值都会消失。
使用异或前，先列出哪些值会出现偶数次、哪些值会留下来；不要把“能异或”误当成“任何重复问题都能异或解决”。
固定位宽
位题首先要分清“数学整数”与“固定宽度位串”。C++ 的 uint32_t 表示无符号 32 位值：每一位都有明确位置，结果会限制在 32 位内；需要这种语义时，应使用无符号类型并显式按题目位宽处理。Python 的 int 则是无限精度整数，不会自然截断为 32 位，负数的位操作也不能直接当作有限位补码结果理解。
因此，题目规定 32 位时，Python 中应主动限制或只循环 32 次；C++ 中也应避免把符号位右移的实现差异带入推理。无论语言如何，先写清循环读多少位、答案保留多少位，再开始编码。
位运算递推
有些量可以从去掉最低位后的更小状态得到。例如对非负 i，i >> 1 去掉最低位，i & 1 给出被去掉的那一位，因此常见模型是 f[i] = f[i >> 1] + (i & 1)。它把一个数的位信息拆成“更短的前缀”和“当前最低位”。
这类递推的关键不在公式本身，而在于确认右移后的状态已经计算过，并确认最低位的贡献确实可以独立相加。若答案依赖完整的固定宽度顺序，则应改用逐位读取、逐位构造的模型。
母题序列
按必学顺序完成下列六题；它们分别练习异或消去、清位、单有效位、位递推、下标配对和固定宽度构造，不在这里重复完整推导：
- 只出现一次的数字：用异或的消去性质留下未配对值。
- 位 1 的个数：重复清除最低位的
1。 - 2 的幂：识别只有一个有效
1的二进制形式。 - 比特位计数：用右移与最低位建立递推。
- 丢失的数字：让值域与下标成对异或消去。
- 颠倒二进制位：在固定 32 位内逐位读取并构造答案。
常见误区
- 只按十进制大小思考，忘记先确定要处理哪一位、共处理多少位。
- 对
n & (n - 1)漏掉n = 0或负数的前提判断。 - 把异或当作加法：异或没有进位，只有逐位不同才为 1。
- 在 Python 中期待整数自动溢出或自动截断为 32 位。
- 翻转位时只处理到最高有效位，遗漏题目要求保留的前导 0。
迁移方向
以后遇到掩码枚举、状态压缩、二进制分组或按位统计时，仍从同一组问题出发：每一位是否独立？位宽是否固定？低位操作后得到的是不是已经求出的更小状态？哪些值能成对抵消？这些判断会把零散技巧整理成可复用的位模型。