C语言位运算：二进制视角下的问题求解

一、从十进制思维到二进制思维日常编程中我们习惯以十进制理解整数。但在位运算的语境下整数不是数值而是位序列。一个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 消除最低位的 1num 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结果为 0int isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }注意必须排除n 0的情况因为 0 和负数不满足此规律。3.4 判断奇偶最低位为 0 是偶数为 1 是奇数if (num 1) // 奇数这本质上是提取最低位后做布尔判断。与% 2相比位运算直接对应 CPU 指令无需除法器参与。3.5 提取最低位的 1int 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消除最低位的 1num (num - 1)提取最低位的 1num (-num)掌握这三个模式配合对操作符本质的理解足以覆盖绝大多数位运算场景。结语位运算的强大不在于技巧或口诀而在于它直接操作数据的物理表示。在 C 语言这种贴近底层的语言中整数不是抽象的数字而是内存中具体的位序列。学会从这个视角审视问题位运算操作符的使用就不再是记忆负担而是自然而然的表达。