位运算技巧与实战
给你两个整数，只用位运算实现加法。你能想到怎么做吗？
大多数人第一反应是 a + b，但如果我告诉你 CPU 底层就是这样算的呢？
为什么面试喜欢考位运算
位运算是计算机最底层的操作，直接作用在二进制位上。面试考察它，往往是想看：
- 你对计算机底层的理解——高级语言封装得太好，反而让人忘了底层原理
- 你对问题本质的洞察——位运算能用最简单的操作解决复杂问题
- 你思维的灵活性——同样一个问题，用位运算往往有巧妙的解法
七种基本位运算
| 符号 | 名称 | 核心用法 |
|---|---|---|
& | 与 | 清零、提取掩码 |
| ` | ` | 或 |
^ | 异或 | 翻转、无进位加法 |
~ | 取反 | 负数转换 |
<< | 左移 | 乘以 2^n |
>> | 无符号右移 | 除以 2^n |
>>> | 有符号右移 | 算术右移 |
经典问题：只用位运算实现加法
题目：不用
+、-运算符，实现两个整数相加。
这是位运算的经典题，核心思想来自二进制加法的本质：
- 无进位加法：
a ^ b（异或） - 进位：
a & b << 1（与后左移一位） - 递归或循环，直到进位为 0
public int add(int a, int b) {
while (b != 0) {
// 异或：计算无进位的加法结果
int sum = a ^ b;
// 与后左移：计算进位
int carry = (a & b) << 1;
a = sum;
b = carry;
}
return a;
}为什么这样能算加法？
二进制加法的每一步：同位相加，结果是异或，产生进位是「与」运算。反复迭代，直到没有进位，就是最终结果。
经典问题：只出现一次的数字
题目：给定一个数组，除了一个数字只出现一次外，其他数字都出现两次。找出那个只出现一次的数字。
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num; // 异或运算
}
return result;
}为什么异或能找到？
a ^ a = 0（相同为 0）a ^ 0 = a（异或 0 不变）- 异或满足交换律和结合律
所以所有成对的数字异或后都变成 0，只剩那个落单的。
进阶：只出现一次的数字 II
题目：其他数字都出现三次，只有一个数字出现一次。找出那个数字。
这次不能再用简单异或了——因为 a ^ a ^ a = a，三次会变回自身。
思路：统计每一位上 1 的个数，模 3 后剩下的就是目标数字该位。
public int singleNumber(int[] nums) {
int result = 0;
// int 有 32 位，统计每一位上 1 的个数
for (int i = 0; i < 32; i++) {
int bitCount = 0;
int mask = 1 << i; // 当前位的掩码
for (int num : nums) {
// 判断 num 的第 i 位是否为 1
if ((num & mask) != 0) {
bitCount++;
}
}
// 如果出现 3 次后余 1，说明目标数字该位是 1
if (bitCount % 3 != 0) {
result |= mask;
}
}
return result;
}为什么取模 3？
因为相同数字都出现 3 次，每一位上 1 的总数一定是 3 的倍数。如果有余数 1，说明目标数字该位是 1。
经典问题：二进制中 1 的个数
题目：统计一个整数二进制中 1 的个数。
方法一：右移位
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1; // 判断最低位是否为 1
n >>>= 1; // 无符号右移
}
return count;
}方法二：n & (n-1) 消除最低位的 1
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // 消除最低位的 1
count++;
}
return count;
}为什么 n & (n-1) 能消除最低位的 1？
n-1 会将 n 最右边的 1 变成 0，其右边所有位变成 1。两者相与，原来最低位的 1 就被消掉了。
经典问题：判断是否是 2 的幂
public boolean isPowerOfTwo(int n) {
// 2 的幂：二进制只有一个 1
// n > 0 && (n & (n-1)) == 0
return n > 0 && (n & (n - 1)) == 0;
}为什么 n & (n-1) == 0 能判断？
2 的幂的二进制只有一个 1（如 8 = 1000）。消除这个 1 后变成 0，所以 n & (n-1) == 0。
经典问题：交换两个整数（不使用临时变量）
public void swap(int a, int b) {
a = a ^ b; // a 变成 a^b
b = a ^ b; // b = (a^b)^b = a
a = a ^ b; // a = (a^b)^a = b
}为什么异或能交换？
利用异或的性质：x ^ x = 0，x ^ 0 = x。
- 第一步：
a = a ^ b - 第二步：
b = (a ^ b) ^ b = a - 第三步：
a = (a ^ b) ^ a = b
注意：如果 a 和 b 指向同一块内存（如 swap(arr[i], arr[i])），会变成 0。
位运算实战技巧
掩码操作
// 获取第 i 位的值（0 或 1）
int getBit(int num, int i) {
return (num >> i) & 1;
}
// 设置第 i 位为 1
int setBit(int num, int i) {
return num | (1 << i);
}
// 设置第 i 位为 0
int clearBit(int num, int i) {
return num & ~(1 << i);
}
// 将第 i 位到第 j 位都置为 1
int updateBits(int num, int i, int j, int newBits) {
int mask = ~0; // 全 1 的掩码
mask = mask << (j - i + 1); // 左移到 j 位置
mask = mask >>> (j - i + 1); // 右移回来，左边补 0
// ... 更多细节省略
}常用技巧
// 判断奇偶：最后一位决定
boolean isOdd(int n) {
return (n & 1) == 1;
}
// 乘以 2 的幂
int multiplyPowerOfTwo(int n, int k) {
return n << k;
}
// 除以 2 的幂
int dividePowerOfTwo(int n, int k) {
return n >> k;
}
// 取绝对值（考虑负数最小值的边界情况）
int abs(int n) {
int sign = n >> 31; // 负数全 1，正数全 0
return (n ^ sign) - sign; // 异或后减 sign
}位运算小结
| 技巧 | 应用 |
|---|---|
n & (n-1) | 消除最低位的 1 |
n & (-n) | 获取最低位的 1 |
n ^ n = 0 | 消除成对出现的数 |
a ^ b ^ a = b | 交换两个变量 |
a & (~0 << k) | 清除低 k 位 |
面试追问预判
Java 中
>>和>>>的区别？>>是算术右移，符号位扩展（负数高位补 1）>>>是逻辑右移，高位补 0
如何判断一个数是否为负数（只用位运算）？
n >> 31 == -1（对于 32 位 int）
为什么负数的二进制表示是补码？
- 补码让加减法统一处理，不需要单独的减法器
记忆口诀
异或相同得 0，异或 0 不变。
n & (n-1)消 1，n & (-n)取 1。移位代替乘除，掩码提取位。
位运算看起来神秘，用熟了就会发现它其实就是「二进制世界的加减乘除」。