位运算
本章题海战术
| 典型例题 | leetcode题目 | leetcode链接 |
|---|---|---|
| 位1的个数 | LeetCode 191 | https://leetcode.cn/problems/number-of-1-bits/description/ |
| 只出现一次的数字 | LeetCode 136 | https://leetcode.cn/problems/single-number/description/ |
| 2 的幂 | LeetCode 231 | https://leetcode.cn/problems/power-of-two/description/ |
| 汉明距离 | LeetCode 461 | https://leetcode.cn/problems/hamming-distance/description/ |
| 颠倒二进制位 | LeetCode 190 | https://leetcode.cn/problems/reverse-bits/description/ |
| 比特位计数 | LeetCode 338 | https://leetcode.cn/problems/counting-bits/description/ |
| 只出现一次的数字 II | LeetCode 137 | https://leetcode.cn/problems/single-number-ii/description/ |
| 丢失的数字 | LeetCode 268 | https://leetcode.cn/problems/missing-number/description/ |
| 只出现一次的数字 III | LeetCode 260 | https://leetcode.cn/problems/single-number-iii/description/ |
| 两整数之和 | LeetCode 371 | https://leetcode.cn/problems/sum-of-two-integers/description/ |
| 子集 | LeetCode 78 | https://leetcode.cn/problems/subsets/description/ |
| 数字范围按位与 | LeetCode 201 | https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/ |
位运算
💡 面试现场口述版
面试官：
说一下你对位运算的理解，以及算法题里常用的位运算技巧？
候选人：
好的面试官。
首先，Java 中的位运算都是基于整数的补码逐位操作，运算效率远高于算术运算，核心价值是极致的空间压缩 —— 比如一个 int 就能存 32 个布尔状态，比数组省几十倍空间。
其次，我最常用的核心技巧有三类：
第一类是 n & (n-1) 消去二进制最右侧的 1，也就是 Brian Kernighan 算法，像位 1 的个数、判断 2 的幂这类题都是直接套这个技巧；
第二类是异或运算，利用「相同数异或为 0、0 异或任何数等于本身」的特性，解决「唯一出现一次的数字」这类问题，空间复杂度能压到 O (1)；
第三类是移位运算，Java 里要特别区分有符号右移 >> 和无符号右移 >>>，负数场景很容易踩坑。
最后，位运算的题型大多是固定套路，核心都是围绕这几个基础技巧延伸的。
🗺️ 位运算核心知识图谱
📊 基础运算符速查表（Java 专属）
| 运算符 | 名称 | 核心规则 | Java 特性说明 | 计算示例 |
|---|---|---|---|---|
& | 按位与 | 两位全为 1，结果才为 1 | 常用于取指定位、掩码过滤 | 6 & 5 = 4（110 & 101 = 100） |
| ` | ` | 按位或 | 两位有 1，结果就为 1 | 常用于设置某一位为 1 |
^ | 按位异或 | 两位不同，结果为 1 | 相同数异或 = 0；0 异或任何数 = 本身 | 6 ^ 5 = 3（110 ^ 101 = 011） |
~ | 按位取反 | 0 变 1，1 变 0 | 包含符号位一起取反，补码下需注意负数 | ~6 = -7 |
<< | 左移 | 各位左移，低位补 0 | 等价于乘以 2 的 n 次方，溢出自动截断 | 6 << 1 = 12 |
>> | 有符号右移 | 各位右移，高位补符号位 | 正数补 0、负数补 1，等价除以 2 取整 | -6 >> 1 = -3 |
>>> | 无符号右移 | 各位右移，高位统一补 0 | Java 独有，负数补 0 后会变成正数 | -6 >>> 1 = 2147483645 |
⚡ 核心技巧与亮点代码
1. Brian Kernighan 算法（消去最右侧的 1）
适用场景：位 1 的个数、2 的幂判断、汉明距离
技术亮点：时间复杂度 O (k)，k 为二进制中 1 的个数，比逐位遍历 O (32) 效率更高，天然兼容负数补码
// 计算二进制中1的个数（LeetCode 191）
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1; // 核心：消去二进制最右侧的1
count++;
}
return count;
}2. 异或特性找唯一出现一次的数字
适用场景：数组中只有一个数出现 1 次，其余都出现 2 次
技术亮点：空间复杂度 O (1)，无需额外哈希表
// 找只出现一次的数字（LeetCode 136）
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num; // 相同数异或抵消，最终剩下唯一出现的数
}
return res;
}3. 纯位运算实现加法
适用场景：禁止使用加减乘除的场景
技术亮点：深度考察补码原理、进位逻辑
// 不用加减乘除做加法（剑指 Offer 65）
public int add(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1; // 计算进位：只有同为1才产生进位，左移1位
a = a ^ b; // 计算无进位和
b = carry; // 进位作为新的加数，循环直到无进位
}
return a;
}⚠️ 技术难点与解决方案
| 技术难点 | 问题描述 | 对应解决方案 |
|---|---|---|
| 负数符号位干扰 | Java 整数以补码存储，有符号右移会补符号位，导致负数位统计、移位结果不符合预期 | 1. 统计位 1 个数优先用 Brian Kernighan 算法，天然兼容补码； 2. 需逐位遍历时用无符号右移 >>> 规避符号位扩展 |
| 移位溢出风险 | 左移超出整数位数时会丢失高位，出现溢出错误；Integer.MIN_VALUE 转正数会溢出 | 1. 大数移位优先用 long 类型承接结果； 2. 2 的幂判断先校验 n > 0 再执行位运算； 3. 除法类题目统一转负数运算，规避最小值溢出 |
| 位状态可读性差 | 用单个整数存储多个状态时，裸写位运算可读性低、维护成本高 | 1. 定义常量掩码，如 static final int MASK_ADMIN = 1 << 2；2. 封装 getBit/setBit/clearBit 工具方法，隐藏底层位运算细节 |
| 多频次位运算易错 | 批量翻转、批量置位时，位偏移量计算容易出错 | 1. 操作前先明确位的下标从 0 开始； 2. 复杂操作拆分成多步单步操作，避免一行写复杂复合运算 |
真实面试模拟
真实面试模拟
😎 面试官：
来，咱们聊聊位运算。你在刷题和项目里应该遇到过不少位操作的场景，能挑几个有代表性的题目说说吗？先从最经典的“找落单数”开始吧。
🧑💻 候选人：
好的。位运算的精髓就是直接在二进制位上做文章，空间通常 O(1)，速度极快。我按核心技巧分类讲吧，先说异或。
🔥 第一板斧：异或（XOR）— 天生找“不同”
😎 面试官：
行，先看最简单的：一个数组里除了一个数出现一次，其他都出现两次，怎么找？LeetCode 136。
🧑💻 候选人：
全员异或就行，成对的数异或变 0，0 异或任何数等于它本身。
public int singleNumber(int[] nums) {
int res = 0;
for (int n : nums) res ^= n;
return res;
}😎 面试官：
如果变成两个落单数呢？比如 260 题。
🧑💻 候选人：
这就得先把所有数异或，得到 x ^ y。然后关键是把两个数分到不同组，让每组退化成一个落单数。分组依据是异或结果中任意一个为 1 的位，常用 diff = xor & -xor 取最低位的 1。
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int n : nums) xor ^= n;
int diff = xor & -xor; // 最低位的1
int x = 0, y = 0;
for (int n : nums) {
if ((n & diff) == 0) x ^= n;
else y ^= n;
}
return new int[]{x, y};
}😎 面试官：
为什么 diff 能保证把两个数分开？会不会某个落单数在两个组都出现？
🧑💻 候选人：
不会。两个数的异或结果在某一位为 1，说明它们在该位一定不同，所以用这一位当掩码，必然一个与掩码与运算得 0，另一个得非 0，天然分成两组。其他成对的数也会根据这一位分到同一组，最后异或消除，每组就剩一个落单数。
😎 面试官：
很好。再看其他数都出现三次，找一个数，137 题呢？
🧑💻 候选人：
这时异或就不够用了，因为成对消除的前提不存在。通用思路是按位统计。每个比特位在所有数字中出现的次数之和，对 3 取模，如果余 1，说明目标数这一位是 1。
public int singleNumber(int[] nums) {
int res = 0;
for (int i = 0; i < 32; i++) {
int cnt = 0;
for (int n : nums) cnt += (n >> i) & 1;
if (cnt % 3 != 0) res |= (1 << i);
}
return res;
}💡 这个方法可以推广：其他数出现 k 次，找一个出现 m 次的数，按位对 k 取模即可。
💪 第二板斧：n & (n - 1) — 专治最低位 1
😎 面试官：
下一个经典技巧，说说 n & (n - 1) 的妙用。
🧑💻 候选人：
它的作用是消掉整数二进制表示中最低位的 1。常用在两个地方：
- 统计 1 的个数（LeetCode 191）
- 判断是否为 2 的幂（LeetCode 231）
// 191. 位1的个数
public int hammingWeight(int n) {
int cnt = 0;
while (n != 0) {
n &= n - 1; // 每次消掉一个最低位1
cnt++;
}
return cnt;
}
// 231. 2的幂
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}😎 面试官：
判断 2 的幂为什么要加 n > 0？直接 (n & (n - 1)) == 0 不行吗？
🧑💻 候选人：
不行，负数肯定不是 2 的幂，但比如 -8 的补码是 11111000，-8 & -9 也可能得 0。所以必须过滤掉非正数。
⚙️ 第三板斧：异或 + 与运算模拟加法
😎 面试官：
那不用加号怎么算两数之和？LeetCode 371。
🧑💻 候选人：
用异或模拟无进位加法，用与运算左移一位得到进位，循环相加直到进位为 0。
public int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1; // 进位
a = a ^ b; // 无进位和
b = carry;
}
return a;
}😎 面试官：
能画个图走一遍吗？比如 3 + 5。
🧑💻 候选人：
a = 3 0011
b = 5 0101
-------------
第一轮：
carry = (0011 & 0101) << 1 = 0001 << 1 = 0010
a = 0011 ^ 0101 = 0110 (6)
b = carry = 0010 (2)
第二轮：
carry = (0110 & 0010) << 1 = 0010 << 1 = 0100
a = 0110 ^ 0010 = 0100 (4)
b = 0100 (4)
第三轮：
carry = (0100 & 0100) << 1 = 0100 << 1 = 1000
a = 0100 ^ 0100 = 0000 (0)
b = 1000 (8)
第四轮：
carry = (0 & 1000) << 1 = 0
a = 0 ^ 1000 = 1000 (8)
b = 0 → 结束，返回 8😎 面试官：
负数也能这么算吗？
🧑💻 候选人：
能，Java 中整数用补码存储，位运算对补码直接操作，所以正负数一样处理，循环也一定能终止。
🎒 第四板斧：位掩码 — 状态压缩的利器
😎 面试官：
再说说怎么用位运算生成所有子集，比如 LeetCode 78。
🧑💻 候选人：
一个整数的每个比特位代表对应元素“选”或“不选”。遍历 0 到 (1 << n) - 1 的所有掩码即可。
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> sub = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) sub.add(nums[i]);
}
res.add(sub);
}
return res;
}😎 面试官：
复杂度呢？适用什么场景？
🧑💻 候选人：
时间复杂度 O(n·2ⁿ)，当 n ≤ 20 时（百万级）可以接受，常用于组合、排列、状态压缩 DP 的枚举。
📊 高频考点总结
🧑💻 候选人：
我把常见位运算题整理成了一张表：
| 题号 | 题目 | 核心技巧 | 易错点 |
|---|---|---|---|
| 136 | 只出现一次的数字 | 全员异或 | - |
| 137 | 只出现一次的数字 II | 按位取模统计 | 注意循环32位 |
| 260 | 只出现一次的数字 III | 异或+低位1分组 | 理解 diff 的作用 |
| 191 | 位1的个数 | n & (n-1) 消1 | 循环条件 n!=0 |
| 231 | 2的幂 | n>0 && (n&(n-1))==0 | 必须判 n>0 |
| 371 | 两整数之和 | 异或求无进位和，与求进位 | 补码下负数循环终止性 |
| 78 | 子集 | 位掩码枚举 | 注意索引偏移 |
| 190 | 颠倒二进制位 | 逐位颠倒 + 无符号右移 | Java 必须用 >>> |
| 201 | 数字范围按位与 | 找公共前缀 | 使用 n & (n-1) 缩小右边界 |
😎 面试官：
总结得不错。最后你用一句话说说位运算面试的诀窍。
🧑💻 候选人：
吃透六个基本操作：& | ^ ~ << >>/>>>，再配合 n & (n-1) 消 1、xor & -xor 取低位 1、按位统计、掩码枚举这四个套路，遇到问题先想二进制表示，基本都能迎刃而解。
😎 面试官：
思路清晰，重点突出，很好 👍，今天先到这里。