一、从十进制思维到二进制思维
日常编程中，我们习惯以十进制理解整数。但在位运算的语境下，整数不是数值，而是位序列。一个int型变量在内存中就是 32 个比特位，每一位独立存在，可以被单独检查、设置、翻转或清除。
这种视角的转换是核心：当你把num = 10看作0000...00001010而不是"十"时，num & 1、num >> 2这些操作的意义就会自然浮现，无需依赖任何外部记忆技巧。
二、异或^：信息的自毁与保留
异或的真值表很简单：相同为 0，不同为 1。但它的代数性质极为强大——满足交换律、结合律，且任何数与自身异或结果为 0，与 0 异或结果不变。
2.1 消除成对重复
在一个数组中，若只有一个数字出现一次，其余均成对出现，整体异或即可得到答案：
int findSingle(int arr[], int n) { int result = 0; for (int i = 0; i < n; i++) result ^= arr[i]; return result; }推导过程本质上是代数化简：
result = a ^ b ^ c ^ a ^ b = (a ^ a) ^ (b ^ b) ^ c = 0 ^ 0 ^ c = c时间复杂度 O(n)，空间复杂度 O(1)。这是理论下界，因为你至少需要遍历一次数组。
2.2 找出两个只出现一次的数字
若有两个唯一数字a和b，整体异或得到a ^ b。由于a != b，这个结果至少有一位为 1。我们取出这个差异位（最低位的 1 即可），用它作为"筛子"把数组分成两组：
int diff = xor_all & (-xor_all); // 提取最低位的 1diff只有一位为 1，其余为 0。数组中每个数与diff做按位与，结果为 0 或非 0，自然分成两类。每类内部再做一次整体异或，分别得到a和b。
2.3 无临时变量交换
利用a ^ b ^ b = a的恒等式：
a = a ^ b; b = a ^ b; // b = (a^b)^b = a a = a ^ b; // a = (a^b)^a = b这展示了异或作为"可逆操作"的特性。但工程实践中不推荐这种写法——可读性损失远大于节省一个整型变量带来的收益。
三、按位与&：掩码与筛选
按位与的核心作用是屏蔽。只要掩码中某位为 0，结果对应位必定为 0；掩码中为 1，结果保留原值。
3.1 提取任意位
int bit = (num >> i) & 1; // 提取第 i 位右移i位把目标位送到最低位，再用& 1屏蔽其余 31 位。这是位操作中最基础的模式。
3.2 消除最低位的 1
num &= num - 1;这是 Brian Kernighan 算法的核心。num - 1会将最低位的 1 借位变成 0，并把其右侧所有 0 变成 1。两者相与，恰好清除最低位的 1，其余高位保持不变。
基于此可以统计 1 的个数：
int countOnes(int num) { int count = 0; while (num) { num &= num - 1; count++; } return count; }循环次数等于二进制中 1 的个数，而非固定 32 次，效率更高。
3.3 判断 2 的幂
2 的幂在二进制中只有一个 1。若n是 2 的幂，n & (n - 1)会消除这个唯一的 1，结果为 0：
int isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }注意必须排除n <= 0的情况，因为 0 和负数不满足此规律。
3.4 判断奇偶
最低位为 0 是偶数，为 1 是奇数：
if (num & 1) // 奇数这本质上是提取最低位后做布尔判断。与% 2相比，位运算直接对应 CPU 指令，无需除法器参与。
3.5 提取最低位的 1
int lowestBit = num & (-num);在补码表示中，-num = ~num + 1。加 1 操作会从最低位开始进位，直到遇到第一个 0 并将其置 1，后续位全变 0。取反后，这个位置恰好与num的最低位 1 对齐。两者相与，只保留这一位。
这个技巧在树状数组（Binary Indexed Tree）和某些位掩码动态规划中非常常见。
四、按位或|与取反~：设置与清除
4.1 设置某一位为 1
构造一个只有第i位为 1 的掩码，与原数相或：
num |= (1 << i);4.2 清除某一位
构造一个只有第i位为 0 的掩码（其余为 1），与原数相与：
num &= ~(1 << i);~按位取反将1 << i的 000...0100...0 变成 111...1011...1，恰好屏蔽第i位。
4.3 翻转某一位
异或 1 翻转，异或 0 保持：
num ^= (1 << i);五、移位操作<<与>>：位的搬运工
移位不是"乘除 2 的快捷方式"——虽然效果上如此，但其本质是位的重新定位。
5.1 提取奇数位与偶数位
// 奇数位：31, 29, 27, ..., 1 for (int i = 31; i >= 1; i -= 2) printf("%d", (num >> i) & 1); // 偶数位：30, 28, 26, ..., 0 for (int i = 30; i >= 0; i -= 2) printf("%d", (num >> i) & 1);i -= 2的步长设计让循环自然跳过相邻位，只访问同奇偶性的位置。右移把目标位送到最低位，& 1完成提取。
六、汉明距离：异或与统计的复合应用
两个整数二进制不同的位数，称为汉明距离。先异或标记差异，再统计 1 的个数：
int hammingDistance(int m, int n) { int xor = m ^ n; int count = 0; while (xor) { xor &= xor - 1; count++; } return count; }这里复合使用了两个核心模式：^标记差异，& (num - 1)消除位计数。
七、统一视角：位运算的设计哲学
回顾上述所有问题，它们共享同一种底层结构：
| 操作符 | 本质作用 | 数学视角 |
|---|---|---|
& | 屏蔽/筛选 | 交集：保留两者都为 1 的位 |
| | 合并/设置 | 并集：任一者为 1 则结果为 1 |
^ | 比较/抵消 | 对称差：不同的位保留，相同的位消除 |
~ | 翻转全集 | 补集：构造反向掩码 |
<<>> | 重新索引 | 位的位置变换 |
当你需要保留某些位时，用&配合掩码；当你需要添加某些位时，用|配合掩码；当你需要消除重复时，用^；当你需要定位某一位时，用移位。
八、三个核心模式
大量位运算问题可以归结为以下三个模式的组合：
提取位：
(num >> i) & 1消除最低位的 1：
num & (num - 1)提取最低位的 1：
num & (-num)
掌握这三个模式，配合对操作符本质的理解，足以覆盖绝大多数位运算场景。
结语
位运算的强大不在于"技巧"或"口诀"，而在于它直接操作数据的物理表示。在 C 语言这种贴近底层的语言中，整数不是抽象的数字，而是内存中具体的位序列。学会从这个视角审视问题，位运算操作符的使用就不再是记忆负担，而是自然而然的表达。
