一、为什么学位运算？
Mermaid · 渲染中（下方为源码）
graph LR A[位运算] --> B[与或非异或] A --> C[移位] B --> D[去最低位/判奇偶/交换] C --> E[乘除以2/取位]
位运算直接操作二进制位，是计算机最底层的运算方式。在算法面试中，位运算题目考查：
- 对二进制表示的理解
- 用 O(1) 空间解决看似复杂的问题
- 代码简洁性与思维灵活性
掌握 6~8 个核心技巧，就能覆盖 90% 的位运算面试题。
二、基本运算速查
| 运算 | 符号 | 示例（Java） | 结果 |
|---|---|---|---|
| 与 AND | & | 5 & 3 → 101 & 011 | 001 = 1 |
| 或 OR | | | 5 | 3 → 101 | 011 | 111 = 7 |
| 异或 XOR | ^ | 5 ^ 3 → 101 ^ 011 | 110 = 6 |
| 取反 NOT | ~ | ~5 | -6 |
| 左移 | << | 1 << 3 | 8 |
| 右移 | >> | 8 >> 2 | 2 |
| 无符号右移 | >>> | -1 >>> 28 | 15 |
异或的核心性质
a ^ a = 0 // 自身异或为 0
a ^ 0 = a // 与 0 异或不变
a ^ b = b ^ a // 交换律
(a ^ b) ^ c = a ^ (b ^ c) // 结合律
异或是位运算题的绝对核心——"出现两次就消掉"。
三、六大核心技巧
3.1 判断奇偶
// n & 1 == 0 → 偶数；n & 1 == 1 → 奇数
boolean isOdd = (n & 1) == 1;3.2 乘除 2 的幂
int doubled = n << 1; // n * 2
int halved = n >> 1; // n / 2（向下取整）
int times8 = n << 3; // n * 83.3 取最低位的 1（lowbit）
int lowbit = n & (-n); // 等价于 n & (~n + 1)应用：树状数组（BIT）的核心操作。
3.4 去掉最低位的 1
n = n & (n - 1); // 清除最右边的 1应用：统计二进制中 1 的个数（Brian Kernighan 算法）。
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}3.5 判断 2 的幂
boolean isPowerOfTwo = n > 0 && (n & (n - 1)) == 0;原理：2 的幂的二进制只有一个 1。
3.6 交换两数（无需临时变量）
a ^= b;
b ^= a;
a ^= b;面试中了解即可，工程中不推荐（可读性差，且对同一变量/同一数组下标做 XOR 交换会清零）。
四、经典面试题
4.1 只出现一次的数字
问题：数组中只有一个元素出现一次，其余出现两次。找出它。
public int singleNumber(int[] nums) {
int xor = 0;
for (int num : nums) xor ^= num;
return xor;
}- 时间：O(n)，空间：O(1)
- 原理：成对的异或消为 0，剩下的就是答案。
4.2 只出现一次的数字 II
问题：其余元素出现三次，找一个出现一次的。
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for (int num : nums) {
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}
return ones;
}- 思路：用两个变量模拟三进制计数器。
4.3 两个只出现一次的数字
问题：恰好两个元素各出现一次，其余出现两次。
public int[] singleNumber(int[] nums) {
int xorAll = 0;
for (int num : nums) xorAll ^= num;
// 取最低位的 1，将数组分成两组
int diff = xorAll & (-xorAll);
int a = 0, b = 0;
for (int num : nums) {
if ((num & diff) == 0) a ^= num;
else b ^= num;
}
return new int[]{a, b};
}- 关键：
xorAll中为 1 的位说明两个答案在该位不同，据此分组。
4.4 缺失数字
问题：[0, n] 中缺了一个数，找出来。
public int missingNumber(int[] nums) {
int xor = nums.length;
for (int i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i];
}
return xor;
}4.5 二进制中 1 的个数
// 方法一：Brian Kernighan
public int hammingWeight(int n) {
int count = 0;
while (n != 0) { n &= (n - 1); count++; }
return count;
}
// 方法二：逐位检查
public int hammingWeight2(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
count += (n >> i) & 1;
}
return count;
}五、位掩码（Bitmask）
用整数的每一位表示一个布尔状态，常用于状态压缩 DP 和集合操作：
int mask = 0;
mask |= (1 << i); // 加入第 i 个元素
mask &= ~(1 << i); // 移除第 i 个元素
boolean has = (mask & (1 << i)) != 0; // 检查第 i 个
mask ^= (1 << i); // 切换第 i 个元素应用：
- 旅行商问题（TSP）状态压缩
- 子集枚举：
for (int sub = mask; sub > 0; sub = (sub - 1) & mask)
六、Java 中的注意事项
| 问题 | 说明 |
|---|---|
| int 是 32 位有符号 | 最高位是符号位 |
>> vs >>> | >> 保留符号，>>> 补 0 |
| 负数的补码 | -n = ~n + 1 |
| 溢出 | 1 << 31 是 Integer.MIN_VALUE |
七、面试常见题
- 🟢 2 的幂、4 的幂、位 1 的个数、缺失数字
- 🟡 只出现一次的数字 I/II/III、二进制加法
- 🟠 最大异或值、子集异或总和、最短超串
- 🔴 最大单词长度乘积（位掩码）、状态压缩 DP
八、调试技巧
- 打印二进制：
Integer.toBinaryString(n)观察位模式。 - 小数据手算：n≤8 时手动画出二进制验证。
- 注意符号：Java 中负数右移用
>>>避免死循环。 - 边界：
Integer.MIN_VALUE取反加一仍为自身（溢出）。