当前位置：首页 > news >正文

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

news 2026/8/15 12:34:47

一、从十进制思维到二进制思维

日常编程中，我们习惯以十进制理解整数。但在位运算的语境下，整数不是数值，而是位序列。一个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); // 提取最低位的 1

diff只有一位为 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
`^`	比较/抵消	对称差：不同的位保留，相同的位消除
`~`	翻转全集	补集：构造反向掩码
`<<>>`	重新索引	位的位置变换