面试
算法思想

位运算算法

# 算法思想 - 位运算

# 1. 基本概念

位运算（Bit Manipulation） 是对二进制位进行直接操作的一类运算。现代编程语言一般提供了对整数（int、long 等）进行按位操作的指令或运算符，它们具有以下典型特征：

执行速度极快：位运算通常是底层 CPU 指令级的操作，相比算术运算往往更高效。
节省空间：在布尔或状态标记等场合，使用位运算可以把多个标记（true/false）压缩到少量比特中。
适用性强：很多算法、数据结构会借助位运算来实现，如位掩码、权限控制、图或集合的状态存储、哈希算法、加密算法等。

常见场景：

快速判断奇偶、乘除以 2、交换数值等基础技巧；
位掩码管理，如集合表示、权限或开关；
位操作实现的数学或逻辑技巧，比如低层级的位翻转、统计二进制中 1 的个数（汉明重量）、判断某些二进制形态（如是否是 2 的幂）。

# 2. 常见位运算符

在大多数编程语言（C/C++、Java、Python 等）中，主要的位运算符有：

&（按位与，Bitwise AND）
- 对应位都为 1 时，结果才为 1，否则为 0。
- 常用来清除某些位（与 0 相与得 0）或保留某些位（与 1 相与保留原位）。
|（按位或，Bitwise OR）
- 只要对应位有一个为 1，则结果为 1，否则为 0。
- 常用来设置某些位为 1，或合并状态（如集合集合做并集）。
^（按位异或，Bitwise XOR）
- 对应位相同则为 0，不同则为 1。
- 常用于翻转某些位（对 1 异或为 0，对 0 异或为 1），或求「不同」的逻辑判断，或实现无额外变量的两数交换。
~（按位取反/补码，Bitwise NOT）
- 0 变为 1，1 变为 0；对所有位执行取反。
- 在有符号数的二进制补码中，~x 表示 -x - 1，要注意符号位的影响。
<<（左移，Left Shift）
- 将所有位向左移动指定次数，高位丢弃，低位补 0。
- 相当于乘以 2 的效果（对无符号或正数而言）。
>>（算术右移，Arithmetic Right Shift）
- 将所有位向右移动，高位用符号位填充（即保留正负号）。
- 相当于除以 2 的效果（对有符号数而言），向下取整。
>>>（逻辑右移，Logical Right Shift，Java/JavaScript 专有）
- 将所有位向右移动，高位用 0 填充，不保留符号位。
- 仅在少数语言（如 Java、JavaScript）使用较多。

# 3. 典型用法

# 3.1 判断奇偶

原理：二进制最右边的一位（最低位）表示奇偶，如果它为 1，则是奇数；如果为 0，则是偶数。

做法：

boolean isEven = (x & 1) == 0; // 若最后一位是0，则偶数，否则奇数

# 3.2 倍数或除以 2

左移 1 位 << 1 相当于乘以 2；
右移 1 位 >> 1 相当于除以 2（有符号数的话会向下取整）。

int y = x << 1; // y = x * 2
int z = x >> 1; // z = x / 2, 向下取整

1
2

# 3.3 无临时变量交换两数

若 a、b在同一块内存中且不指向同一地址，可以用异或交换技巧。

a = a ^ b;
b = a ^ b; // 等价于原来的 a
a = a ^ b; // 等价于原来的 b

1
2
3

不过在实践中要小心，若 a 和 b 是同一块内存时，会导致结果变为 0。

# 3.4 取绝对值或带符号运算

取绝对值可以通过判断符号位 + 位操作实现：

// C 例子：如果 x < 0，则 x ^ -1 + 1, 这就是取负数的补码
// 实际上更常见直接用内置函数 abs()，但这里示例位运算思路。
int mask = x >> 31;  // 若 x >= 0，mask = 0; 若 x < 0，mask = -1 (全1)
int absX = (x ^ mask) - mask;

1
2
3
4

原理：当 mask = -1 时，相当于对 x 取反再加 1（即负数的二进制补码计算）。

# 3.5 统计二进制中 1 的个数（汉明权/Hamming Weight）

常规循环：每次判断最低位是否为 1，然后右移一位：

int count = 0, tmp = x;
while (tmp != 0) {
    count += (tmp & 1);
    tmp >>>= 1; // 无符号右移，或者算术右移也可
}

1
2
3
4
5

Brian Kernighan 算法：每次执行 n & (n - 1) 可以去掉 n 最右侧的一个 1 位：
```
int count = 0, tmp = x;
while (tmp != 0) {
    tmp = tmp & (tmp - 1);
    count++;
}
```
1
2
3
4
5
- 这样只循环 1 的个数次，更高效。

# 3.6 判断某数是否是 2 的幂

若 n 是 2 的幂，则它的二进制形式只有一个 1，如：1(0b0001),2(0b0010),4(0b0100),8(0b1000)…

判断方式：

// n > 0 && (n & (n - 1)) == 0
boolean isPowerOfTwo = (n > 0) && ((n & (n - 1)) == 0);

1
2

原理：n & (n - 1) 会抹去 n 最右侧的 1；如果是 2 的幂，则只会有一个 1，抹去后就变成 0。

# 3.7 位掩码（Bitmask）技巧

使用一个整型变量的不同位来表示集合、权限或状态。例如有 n 个元素，使用一个 int mask，若第 i 位是 1 表示该元素被选中。
添加元素：mask |= (1 << i);
删除元素：mask &= ~(1 << i);
判断元素是否在集合中：(mask & (1 << i)) != 0
这样可以在常数时间内判断、合并子集等操作。枚举时可循环 0..(1<<n)-1 即可遍历所有子集。

# 4. 常见位运算技巧

低位提取
- 想要获取二进制数的最低 k 位，可以与 ((1 << k) - 1) 进行按位与。
- 例：x & 0xFF 提取最低 8 位，用于获取一个 int 的最低字节。
高位清除
- 若要清除二进制数的高位，只保留某些较低位，也可用相同的「与 (1<<k) - 1」思路。
翻转指定位
- 用 mask 表示要翻转的位，然后 x ^= mask 实现翻转（如果位是 1 则变 0，反之变 1）。
奇偶校验
- 按位异或可以用来做奇偶校验，每来一个 bit 就跟结果异或一下，最终若结果是 1，则奇数个 1；若结果是 0，则偶数个 1。
快速清零
- 当我们要清除最低位的 1，可以执行 x & (x - 1)；
- 当我们要仅保留最低位的 1，可以执行 x & (-x)（在补码表示下，-x 为 ~x + 1，会提取出最低的 1）。

# 5. 典型应用及复杂度

用法	代码示例	复杂度	备注
奇偶判断	`(x & 1) == 0`	O(1)O(1)	几乎是 CPU 指令级
乘除 2	`x << 1`, `x >> 1`	O(1)O(1)	小心符号位
交换两数	`a ^= b; b ^= a; a ^= b;`	O(1)O(1)	避免 a、b 同地址
统计二进制中 1 的个数	`x &= (x - 1)` 循环	与位数中 1 的个数成正比	常用 Brian Kernighan 算法
判断是否是 2 的幂	`(x & (x - 1)) == 0 && x > 0`	O(1)O(1)	只能检测正数 2 的幂
位掩码表示子集	`mask` 里每位代表集合中某元素	需遍历 `2^n`	常用在枚举场景
翻转指定位	`x ^= (1 << i)`	O(1)O(1)	i 为位索引
抹去最低位的 1	`x = x & (x - 1)`	O(1)O(1) / 次	每次操作去掉一个 1
保留最低位的 1	`lowest = x & (-x)`	O(1)O(1)	取出最右边的 1
取绝对值（特例）	`int mask = x >> 31; x = (x ^ mask) - mask;`	O(1)O(1)	不建议滥用（可用 Math.abs）

# 6. 位运算的优缺点

优点：

高效：CPU 对位操作有硬件级支持，速度通常极快。
节省空间：可以在一个整型变量的位上存储多个布尔或开关状态。
表达灵活：在枚举子集、图状态压缩、密码学操作等，位运算都提供了很大灵活性。

缺点：

可读性低：位掩码、位移等操作往往不如高级语义直接，需要仔细理解；
容易出错：如越界移位、符号位处理、负数补码影响等，需要格外小心；
不易维护：对复杂的位运算代码做修改，需要谨慎且详细的注释。

编辑此页

上次更新: 2025/01/05, 02:09:04

← 分治算法滑动窗口模板→