位运算高频题 - 面试题

#

★★★

1. 只出现一次的数字（LeetCode 136）中异或的三条性质如何保证成对元素抵消，为什么不需要额外空间？

问题

只出现一次的数字，说明异或的三条性质如何保证成对元素抵消，以及为何不需要额外空间？

考察点

异或三条性质
成对元素抵消
O(1) 空间

答案

只出现一次的数字：数组中除了一个元素出现一次，其余都出现两次，求该元素。用异或：对所有元素做异或，结果就是只出现一次的元素。异或三条性质：① 交换律/结合律（a⊕b = b⊕a、(a⊕b)⊕c = a⊕(b⊕c)）；② 自反性（a⊕a=0）；③ 恒等（a⊕0=a）。由性质②，成对出现的相同元素异或为 0；由性质③，0 与只出现一次的元素异或为该元素本身。所有元素异或 = (成对元素异或为 0) ⊕ (单次元素) = 单次元素。不需要额外空间：只用了一个变量存异或结果，无需哈希表或数组，O(1) 空间。O(n) 时间。

解析

异或的"自反性"（a⊕a=0）是本题核心：成对元素自消，单次元素保留。三条性质结合保证一次遍历即可。这是"位运算替代哈希表"的经典 O(1) 空间解法。

示例代码

int singleNumber(int[] nums) {
    int res = 0;
    for (int x : nums) res ^= x; // 成对抵消，单次保留
    return res;
}

#

★★★

2. 位 1 的个数（LeetCode 191）中 n & (n-1) 循环清零最低位与查表法、内置 popcount 的取舍？

问题

位 1 的个数，说明 n & (n-1) 循环清零最低位与查表法、内置 popcount 的取舍？

考察点

n & (n-1) 清零最低位
查表法
内置 popcount

答案

位 1 的个数（汉明重量）：n & (n-1) 循环清零最低位的 1：每次 n = n & (n-1) 把最低位的 1 变成 0，循环次数 = 1 的个数。复杂度 O(1 的个数)，最坏 O(位数)。查表法：预计算 8 位（或 16 位）的 popcount 表，每 8 位查表累加，O(位数/8) 次查表。取舍：① n&(n-1) 循环简单、无需建表，适合"1 少"的场景；② 查表法固定 O(位数/8) 次查表，适合"1 多"或需固定时间；③ 内置 Integer.bitCount 用硬件指令（popcnt）最块，O(1)，但依赖平台。选型看场景：一般用 n&(n-1) 或内置，查表适合需要可控常数或跨平台。

解析

n&(n-1) 是"清零最低位 1"的经典技巧，复杂度与 1 的个数成正比。查表法预处理分块，内置 popcount 用硬件指令。三者体现"时间、空间、硬件加速"的取舍。

示例代码

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) { n &= (n - 1); count++; } // 清零最低位 1
    return count;
}

#

★★★

3. 比特位计数（LeetCode 338）中 dp[i]=dp[i>>1]+(i&1) 的递推如何 O(n) 求出所有结果？

问题

比特位计数，说明 dp[i]=dp[i>>1]+(i&1) 的递推如何 O(n) 求出所有结果？

考察点

递推公式 dp[i]=dp[i>>1]+(i&1)
最高位/最低位递推
O(n) 复杂度

答案

比特位计数：求 0..n 每个数的 1 的个数。递推 dp[i]=dp[i>>1]+(i&1)：i>>1 是 i 去掉最低位后的数，dp[i>>1] 是它的 1 个数，i&1 是 i 最低位的 1（0 或 1）。故 dp[i] = dp[i>>1] + i 的最低有效位。O(n) 时间、O(n) 空间。这个递推利用了"i 的位 = i>>1 的位 + 最低位"的关系，因为 i 与 i>>1 的关系是"去掉最低位"，二者 1 的个数就差最低位。从 i=1 到 n 顺序填表即可。

解析

递推核心是"i 与 i>>1 的位关系"：i 去掉最低位后是 i>>1，1 的个数差最低位 (i&1)。这使每数 O(1) 递推，总 O(n)。也可用 dp[i]=dp[i&(i-1)]+1（去掉最低位 1）等变体。体现"位运算递推"。

示例代码

int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1); // 递推
    return dp;
}

#

★★★

4. 两数之和不用加号（371）中异或得无进位和、与左移得进位，递归终止条件如何设计

问题

两数之和不用加号，说明异或得无进位和、与左移得进位，以及递归终止条件如何设计？

考察点

a^b 无进位和
a&b<<1 进位
递归直到无进位

答案

两数之和不用加号：a+b = 无进位和 + 进位。无进位和 = a^b（异或）；进位 = (a&b)<<1（与得同时为 1 的位，左移一位是进位）。递归：sum = a^b，carry = (a&b)<<1；若 carry 为 0 则返回 sum，否则递归求 sum+carry。终止条件：carry 为 0（无进位）时，a^b 即最终结果。迭代写法：while(b!=0){ carry=(a&b)<<1; a=a^b; b=carry; }。负数也可用（Java 补码，移位自动处理）。

解析

加法分两步：无进位和（异或）+ 进位（与左移）。进位不为 0 则继续加，直到进位为 0。终止条件就是"carry 为 0"。这是"位运算实现加法"的经典，体现"异或=逐位加、与=进位"。

示例代码

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1; // 进位
        a = a ^ b;                // 无进位和
        b = carry;
    }
    return a;
}

#

★★

5. 只出现一次的数字 II（LeetCode 137）中按位统计 1 的个数并对 3 取模能找出单次元素，如何推广到出现 k 次？

问题

只出现一次的数字 II，说明为何按位统计 1 的个数并对 3 取模能找出单次元素，以及如何推广到出现 k 次？

考察点

按位统计 1 的个数
mod 3
推广到 k 次

答案

只出现一次的数字 II：除一个元素出现一次外，其余都出现三次，求该元素。按位统计：对每一位，统计所有元素在该位为 1 的个数，若该位 1 的个数 mod 3 == 1，则单次元素在该位为 1；否则为 0。原理：出现三次的元素，其每一位贡献的 1 的个数是 3 的倍数，mod 3 为 0；单次元素贡献 mod 3 为 1。故对每位取 mod 3 即可还原单次元素。推广到出现 k 次：对每位统计 1 的个数 mod k，若 mod k == 1 则单次元素该位为 1。用 32 位数组统计，O(32·n) 时间，O(1) 空间。也可用"数字电路"（ones/twos 状态机）优化到 O(n) 时间 O(1) 空间。

解析

核心是把"出现次数"按位模化：出现 3 次的元素每位的贡献是 3 的倍数，mod 3 归零，单次元素保留。推广到 k 次只需 mod k。这是"按位统计 + 取模"的通用解法。

示例代码

int singleNumber(int[] nums) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        for (int x : nums) sum += (x >> i) & 1;
        if (sum % 3 == 1) res |= (1 << i); // 该位 mod 3 = 1
    }
    return res;
}

#

★★

6. 只出现一次的数字 III（LeetCode 260）中如何用“最低不同位”把两个单次元素分到两组异或？

问题

只出现一次的数字 III，说明如何用"最低不同位"把两个单次元素分到两组异或？

考察点

全部异或得两单次的异或
找最低不同位
分组异或

答案

只出现一次的数字 III：除两个元素各出现一次外，其余出现两次，求两个单次元素。① 全部异或得 a^b（两个单次元素的异或，成对元素抵消）；② 找 a^b 的最低不同位：diff = a^b 的二进制中最低的 1 位（如 diff = a^b & (-(a^b))），该位 a 与 b 不同；③ 按 diff 位分组：把数组分成"该位为 1"与"该位为 0"两组，两个单次元素必分到不同组（因该位不同），每组内其他元素成对出现；④ 各组异或得两个单次元素。原理：最低不同位作为分组依据，把 a、b 分开，且每组内成对元素抵消。

解析

核心是"用 a^b 的最低不同位分组"：该位 a、b 不同，故分到两组；每组内除一个单次元素外其余成对，异或抵消后得单次元素。这是"异或 + 最低位分组"的经典。

示例代码

int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int x : nums) xor ^= x;
    int diff = xor & (-xor); // 最低不同位
    int a = 0, b = 0;
    for (int x : nums) {
        if ((x & diff) == 0) a ^= x; // 该位为 0 组
        else b ^= x;                 // 该位为 1 组
    }
    return new int[]{a, b};
}

#

★★

7. 颠倒二进制位（LeetCode 190）中逐位取出逆序拼接的实现与复杂度？

问题

颠倒二进制位，说明逐位取出逆序拼接的实现与复杂度？

考察点

逐位取出
逆序拼接
O(1) 复杂度

答案

颠倒二进制位：把 32 位整数的二进制位颠倒。① 逐位法：循环 32 次，每次取 n 的最低有效位（n&1），加到结果 res 的最高位（res = (res<<1)|(n&1)），然后 n>>=1。② 分治/交换法：交换高低 16 位、再 8 位、4 位、2 位、1 位（rank 交换），用掩码一次完成。复杂度：逐位 O(32)，分治 O(log 32)=O(5)。逐位法直观，分治法更快。用无符号右移处理符号位。

解析

逐位法每次取最低位拼到结果，循环 32 次固定 O(32)。分治法用"对半交换"把复杂度降到 O(log 32)。核心是"取出最低位 + 结果左移拼接"。用 >>> 处理负数。

示例代码

int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1); // 拼到结果
        n >>>= 1;                    // 无符号右移
    }
    return res;
}

#

★★

8. 缺失数字（LeetCode 268）中异或法与高斯求和法的原理与溢出风险对比？

问题

缺失数字，说明异或法与高斯求和法的原理与溢出风险对比？

考察点

异或法
高斯求和法
溢出风险

答案

缺失数字：0..n 中缺一个数，求它。异或法：先异或 0..n（所有数），再异或数组中的数，两两抵消，剩下的就是缺失数。原理：a^a=0、a^0=a，缺失数只出现一次（在 0..n 中）而数组中没有它，故异或结果 = 缺失数。O(n) 时间、O(1) 空间，无溢出。高斯求和法：sum = n(n+1)/2（0..n 的和），减去数组中所有数的和，差值即缺失数。O(n) 时间、O(1) 空间。溢出风险：高斯求和法当 n 很大时 n(n+1)/2 可能溢出 int（需用 long 或大数），异或法无溢出（异或不产生中间大数）。故异或法在溢出风险上更安全。

解析

异或法利用"自反性"抵消成对、保留缺失；高斯求和法用"总和差"，但需防溢出。异或法无加法溢出，更稳健。这是"位运算 vs 数学"的对比，溢出风险是区分点。

示例代码

int missingNumber(int[] nums) {
    int res = 0;
    for (int i = 0; i <= nums.length; i++) res ^= i; // 0..n
    for (int x : nums) res ^= x;                      // 抵消存在
    return res;
}
// 高斯求和：long sum = n*(n+1)/2; sum -= 数组和; 差值即缺失

#

★★

9. 2 的幂（LeetCode 231）中 n>0 且 n&(n-1)==0 的判定，扩展到 4 的幂（342）如何加掩码？

问题

2 的幂判定，说明 n>0 且 n&(n-1)==0 的判定，以及扩展到 4 的幂如何加掩码？

考察点

2 的幂判定
4 的幂掩码
位运算

答案

2 的幂：n 是 2 的幂当且仅当 n>0 且 n&(n-1)==0。n&(n-1) 清零最低位 1，若 n 是 2 的幂则只有一位 1，清零后为 0。例：4(100)&3(011)=0。4 的幂：4 的幂是 2 的幂且 1 在奇数位（0 位、2 位、4 位...）。判断：① n>0 且 n&(n-1)==0（是 2 的幂）；② 1 在奇数位，用掩码 n&(0x55555555)!=0（0x55555555 是奇数位为 1）或 n%3==1（4^k mod 3 = 1）。即 4 的幂 = 2 的幂 + 奇数位掩码。

解析

2 的幂用"n&(n-1)==0"（唯一一位 1）。4 的幂在 2 的幂基础上要求"1 在奇数位"，用掩码 0x55555555 或 n%3==1 判断。这是"位判定"的扩展。

示例代码

boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0; }

#

★★

10. 汉明距离（LeetCode 461）中异或后统计 1 的个数，与内置 Integer.bitCount 的实现差异？

问题

汉明距离，说明异或后统计 1 的个数，与内置 Integer.bitCount 的实现差异？

考察点

异或求不同位
统计 1 个数
与 bitCount 差异

答案

汉明距离：两个整数二进制位不同的个数。做法：异或 x^y 得到不同位为 1 的结果，再统计其中 1 的个数（popcount）。统计 1 个数：① 循环 n&(n-1) 清零最低位，O(1 的个数)；② 逐位统计，O(位数)；③ 内置 Integer.bitCount，用分治/硬件指令（popcnt），O(1) 最快。差异：手写循环（n&(n-1) 或逐位）简单但依赖位数/1 个数；内置 bitCount 用"分治累加"（5 次掩码运算）或硬件 popcnt 指令，固定 O(1) 且更快。工程上用 bitCount 最省事，手写体现原理。

解析

汉明距离 = 异或后 popcount。统计 1 个数的实现差异：手写循环（n&(n-1)）与内置 bitCount（分治/硬件）。bitCount 用"每 2 位、4 位、8 位分组累加"的分治技巧，O(1)。

示例代码

int hammingDistance(int x, int y) {
    int diff = x ^ y; // 不同位
    int count = 0;
    while (diff != 0) { diff &= (diff - 1); count++; } // 统计 1 个数
    return count;
}

#

★★

11. 数字范围按位与（LeetCode 201）中结果是公共前缀部分，如何用右移找公共前缀？

问题

数字范围按位与，说明为何结果是公共前缀部分，以及如何用右移找公共前缀？

考察点

按位与结果 = 公共前缀
右移找公共前缀
边界

答案

数字范围按位与 [left,right]：结果 = left 与 right 的公共前缀（二进制前缀相同部分），后缀补 0。原理：在 [left,right] 范围内，从某位开始有进位变化，导致该位及之后所有位在范围内出现过 0 与 1，按位与后这些位为 0；只有公共前缀（未变化的位）保持。故结果 = 公共前缀后接 0。找公共前缀：用右移——不断把 left 和 right 同时右移，记录移位数，直到 left==right（找到公共前缀），结果 = left << 移位数。复杂度 O(位数)。

解析

按位与结果只看公共前缀，因为范围内的进位使后缀位同时出现 0/1 而被清零。右移找公共前缀：同时右移直到相等，再左移回去。这是"按位与 + 公共前缀"的经典。

示例代码

int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) { left >>= 1; right >>= 1; shift++; } // 找公共前缀
    return left << shift; // 前缀后补 0
}

#

★★

12. 最大单词长度乘积（LeetCode 318）中如何用 int 位掩码表示字母集合，预计算后 O(n²) 判交集？

问题

最大单词长度乘积，说明如何用 int 位掩码表示字母集合，预计算后 O(n²) 判交集？

考察点

int 位掩码表示字母集合
预计算掩码
O(n²) 判交集

答案

最大单词长度乘积：两个单词无公共字母时，求长度乘积最大。用 int 位掩码表示字母集合：每个单词用一个 int，第 k 位为 1 表示含字母 'a'+k。预计算每个单词的掩码。判断两词无公共字母：掩码相与 == 0（无相同字母位）。O(n²) 遍历所有单词对，若掩码相与为 0 则更新最大长度乘积。复杂度：预计算 O(n·L)（L 为词长），判交集 O(n²)。位掩码代替"集合比较"，把"是否含相同字母"从 O(26) 降到 O(1)（一次按位与）。

解析

关键是用 int 位掩码编码字母集合：26 个字母用 26 位，无公共字母即掩码 & == 0。位掩码把集合比较降为 O(1) 按位与。这是"位掩码优化集合操作"的经典。

示例代码

int maxProduct(String[] words) {
    int[] mask = new int[words.length];
    for (int i = 0; i < words.length; i++)
        for (char c : words[i].toCharArray()) mask[i] |= 1 << (c - 'a');
    int max = 0;
    for (int i = 0; i < words.length; i++) for (int j = i + 1; j < words.length; j++)
        if ((mask[i] & mask[j]) == 0) max = Math.max(max, words[i].length() * words[j].length());
    return max;
}

#

★★

13. 二进制求和（LeetCode 67）中模拟逐位加法时进位如何传递，与“大数加法”模板的关系？

问题

二进制求和，说明模拟逐位加法时进位如何传递，以及与"大数加法"模板的关系？

考察点

逐位相加进位
进位传递
与大数加法模板关系

答案

二进制求和：两个二进制字符串相加。模拟逐位加法：从最低位开始，逐位把两个串的对应位与进位相加，得 sum = a+b+carry，结果位 = sum%2，进位 = sum/2。直到两串都处理完且进位为 0。结果逆序。这与"大数加法"（十进制）模板完全同构：都是"从低位逐位相加 + 进位 + 处理进位"，只是进制不同（十进制 sum%10、carry=sum/10；二进制 sum%2、carry=sum/2）。二进制加法是"大数加法模板"的 2 进制特例。

解析

二进制求和是大数加法的 2 进制版：逐位 + 进位 + 模基数。模板通用（任意进制），只改基数。进位传递：sum/基数作为下一位进位。理解"通用大数加法模板"可迁移到任意进制。

示例代码

String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;
        if (i >= 0) sum += a.charAt(i--) - '0';
        if (j >= 0) sum += b.charAt(j--) - '0';
        sb.append(sum % 2); carry = sum / 2; // 二进制进位
    }
    return sb.reverse().toString();
}

#

★★

14. 最大异或对（421）中 01-Trie 逐位贪心与哈希前缀法如何达到 O(n log A)，为什么贪心最优

问题

最大异或对，说明 01-Trie 逐位贪心与哈希前缀法如何达到 O(n log A)，以及为何贪心最优？

考察点

01-Trie 逐位贪心
哈希前缀法
O(n log A) 与贪心最优

答案

最大异或对：数组中两个数异或的最大值。01-Trie 法：把每个数字的二进制位插入 Trie（从高位到低位），对每个数，在 Trie 中沿"尽量取相反位"的路径贪心求最大异或。贪心最优：异或最大化应从高位到低位尽量取 1，而高位的 1 优先于低位所有位（二进制权重），故逐位贪心（高位优先）是最优。O(n log A)（A 为最大数，log A 为位数）。哈希前缀法：从高位到低位，维护已出现的前缀集合，判断是否存在使当前位为 1 的前缀组合，O(n log A)。两种都 O(n log A)。01-Trie 直观，哈希前缀更省空间。

解析

最大异或的贪心最优性：二进制高位权重决定一切，逐位取最大（先保证高位 1）即最优。01-Trie 每次沿相反位走，哈希前缀法用集合验证。复杂度 O(n log A) 由"每位数遍历"决定。

示例代码

// 01-Trie 插入 + 查询
class TrieNode { TrieNode[] ch = new TrieNode[2]; }
void insert(int x) { TrieNode cur = root; for (int i = 31; i >= 0; i--) { int b = (x >> i) & 1; if (cur.ch[b] == null) cur.ch[b] = new TrieNode(); cur = cur.ch[b]; } }
int query(int x) { TrieNode cur = root; int res = 0; for (int i = 31; i >= 0; i--) { int b = (x >> i) & 1; if (cur.ch[1 - b] != null) { res |= (1 << i); cur = cur.ch[1 - b]; } else cur = cur.ch[b]; } return res; }

#

★★

15. UTF-8 验证（393）中按首字节前缀位数判断后续字节个数，非法序列的边界分类

问题

UTF-8 验证，说明按首字节前缀位数判断后续字节个数，以及非法序列的边界分类？

考察点

首字节前缀位数决定字节数
连续字节校验
非法分类

答案

UTF-8 验证：判断数组是否为合法 UTF-8 编码。规则：① 首字节：0xxxxxxx（单字节）、110xxxxx（2 字节）、1110xxxx（3 字节）、11110xxx（4 字节）；② 后续字节必须以 10xxxxxx 开头。算法：遍历，根据首字节前缀位的 1 的个数确定后续字节数（1 个 0 开头=1 字节，110 开头=2，1110=3，11110=4）；检查后续字节数是否在 1-4 且剩余字节够，且每个后续字节都以 10 开头。非法分类：① 首字节前缀非法（如 11111 开头或 10 开头当首字节）；② 后续字节数不足或超出 4；③ 后续字节不以 10 开头；④ 首字节为 10 开头（说明是孤立的后续字节）。按这些边界逐类检查。

解析

UTF-8 验证核心是"首字节前缀位数决定序列长度 + 后续字节 10 前缀校验"。非法分类包括首字节前缀错误、长度越界、后续字节前缀错误。这是"字节编码 + 边界校验"的题。

示例代码

boolean validUtf8(int[] data) {
    int i = 0;
    while (i < data.length) {
        int first = data[i];
        int n = 0;
        if ((first >> 5) == 0b110) n = 1;       // 2 字节
        else if ((first >> 4) == 0b1110) n = 2; // 3 字节
        else if ((first >> 3) == 0b11110) n = 3;// 4 字节
        else if ((first >> 7) != 0) return false; // 非法首字节
        if (i + n >= data.length) return false;  // 长度不足
        for (int k = 1; k <= n; k++) if ((data[i + k] >> 6) != 0b10) return false; // 后续字节
        i += n + 1;
    }
    return true;
}

#

★

16. 格雷编码（LeetCode 89）中 G(n)=i^(i>>1) 的构造为什么保证相邻码只差一位？

问题

格雷编码，说明 G(n)=i^(i>>1) 的构造为何保证相邻码只差一位？

考察点

格雷码定义
G(n)=i^(i>>1) 构造
相邻差一位证明

答案

格雷编码：相邻两个数二进制只差一位的序列。G(n)=i^(i>>1) 是标准构造：第 i 个格雷码 = i^(i>>1)。为何相邻只差一位：考虑 i 与 i+1，i+1 是 i 加 1，二进制从最低位开始有一段连续的 1 变成 0，并在其前一位 0 变成 1。设 i 的最低连续 1 段从第 k 位开始，则 i 与 i+1 在低于 k 的位都翻转（1→0），第 k 位 0→1。对 G(i)=i^(i>>1) 与 G(i+1)=(i+1)^((i+1)>>1)，可以证明差异恰好在于第 k 位（其余位相同）：因为 i 右移一位后，i+1 的进位把第 k 位的影响传递，使得 G(i) 与 G(i+1) 在低于 k 位相同、第 k 位不同。直观验证：G(0)=0, G(1)=1, G(2)=3, G(3)=2，相邻 0-1-3-2 各差一位。数学上，i^(i>>1) 的构造保证"加 1 的进位只影响一位格雷码位"。

解析

G(n)=i^(i>>1) 的构造基于"i 加 1 的进位模式"：连续的 1 变 0 在右移后与原来的异或抵消，只留下进位所在位翻转。故相邻格雷码只差一位。这是"位运算构造"的经典题。

示例代码

List<Integer> grayCode(int n) {
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < (1 << n); i++) res.add(i ^ (i >> 1)); // G(n)=i^(i>>1)
    return res;
}

#

★

17. 子集（LeetCode 78）位枚举中 mask 从 0 到 2^n-1 枚举子集的顺序与回溯法的对比？

问题

子集的位枚举，说明 mask 从 0 到 2^n-1 枚举子集的顺序，以及与回溯法的对比？

考察点

位掩码枚举子集
mask 0..2^n-1
与回溯对比

答案

子集位枚举：集合有 n 个元素，用 n 位掩码 mask 表示一个子集（第 k 位=1 表示含第 k 个元素）。遍历 mask 从 0 到 2^n-1，每个 mask 对应一个子集，提取其中 1 的位。枚举顺序：从 0（空集）到 2^n-1（全集），按数值递增，即按"二进制字典序"枚举（先空集、再单元素、再组合...）。复杂度 O(n·2^n)。与回溯法对比：回溯用"选/不选"递归生成子集，按树形顺序；位枚举用循环 mask 直接生成，按数值顺序。两者都生成全部 2^n 个子集，位枚举更简洁（无递归）、适合 n 较小（n≤20，2^n 可控）；回溯更灵活（可剪枝、可处理去重）。顺序不同：位枚举按 mask 数值递增，回溯按递归分支顺序。

解析

位枚举用"mask 数值"直接代表子集，从小到大遍历即枚举全部子集。与回溯的树形递归对比，位枚举是迭代式、顺序确定，但需提取位。适合 n 小，回溯适合剪枝/去重。

示例代码

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    for (int mask = 0; mask < (1 << nums.length); mask++) {
        List<Integer> sub = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) if ((mask & (1 << i)) != 0) sub.add(nums[i]);
        res.add(sub);
    }
    return res;
}

#

★

18. 二进制手表（LeetCode 401）中枚举小时与分钟的组合，如何统计亮灯数？

问题

二进制手表，说明枚举小时与分钟的组合，如何统计亮灯数？

考察点

小时 0-11、分钟 0-59
枚举组合
统计亮灯（popcount）

答案

二进制手表：小时由 4 个 LED 表示（0-11），分钟由 6 个 LED 表示（0-59），求"亮灯数恰好为 turnedOn"的所有时间。做法：枚举小时 h 从 0 到 11、分钟 m 从 0 到 59，统计 h 的亮灯数（popcount(h)）+ m 的亮灯数（popcount(m)），若等于 turnedOn 则加入结果。popcount 用 Integer.bitCount 或 n&(n-1) 循环。复杂度 O(12×60) 固定。输出格式：h:m，分钟补零（如 1:05）。

解析

二进制手表是"枚举 + popcount"：小时/分钟范围固定，枚举所有组合，统计亮灯数匹配。popcount 统计二进制 1 的个数。范围小、枚举简单。输出去重与格式是细节。

示例代码

List<String> readBinaryWatch(int turnedOn) {
    List<String> res = new ArrayList<>();
    for (int h = 0; h < 12; h++) for (int m = 0; m < 60; m++) {
        if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
            res.add(h + ":" + (m < 10 ? "0" : "") + m);
        }
    }
    return res;
}

#

★

19. 数字转换为十六进制（LeetCode 405）中负数用补码如何逐 4 位转换？

问题

数字转换为十六进制，说明负数用补码如何逐 4 位转换？

考察点

逐 4 位转换
负数补码
无符号右移

答案

数字转换为十六进制：把整数转成 16 进制字符串，负数用补码（32 位无符号）。做法：循环处理，每 4 位一组（低 4 位），取 n & 0xF 得到十六进制位，映射到字符，然后 n >>>= 4（无符号右移，保证负数补码正确）。循环直到 n 为 0 或处理完 32 位。负数：用无符号右移 >>> 处理补码，取出的是 32 位补码的 16 进制表示。例 -1 的补码是 0xFFFFFFFF。用 >>> 而非 >>，因为 >> 负数会补符号位导致死循环。

解析

十六进制转换 = 每 4 位一组提取。负数用补码 + 无符号右移 >>>（避免符号位扩展死循环）。与"十进制转任意进制"模板同构，只是每次取 4 位。用 >>> 处理负数是关键。

示例代码

String toHex(int num) {
    if (num == 0) return "0";
    char[] map = "0123456789abcdef".toCharArray();
    StringBuilder sb = new StringBuilder();
    while (num != 0) {
        sb.append(map[num & 0xF]); // 低 4 位
        num >>>= 4;                 // 无符号右移
    }
    return sb.reverse().toString();
}

#

★

20. 两数相除（29）中如何用倍增减法（二进制长除）在 32 位范围内实现，溢出边界如何处理

问题

两数相除，说明如何用倍增减法（二进制长除）在 32 位范围内实现，以及溢出边界如何处理？

考察点

倍增减法（二进制长除）
32 位范围
溢出边界

答案

两数相除：不能用乘除模，求商。倍增减法（二进制长除）：把除数不断翻倍（用左移），找到最大的"不超过被除数"的倍数，累加商，被除数减去该倍数，重复。启发式：内层循环把 d 翻倍直到超过 t，商累加对应的 2^k。溢出边界：① 被除数 = Integer.MIN_VALUE、除数 = -1 时，商为 2^31 溢出，应返回 Integer.MAX_VALUE；② 用 long 存中间值避免翻倍溢出。处理符号：先取绝对值（用 long），统一正数除法，最后按符号调整。循环终止：被除数减到 0 或小于除数。

解析

倍增减法把除法转成"加减 + 移位"的二进制长除：除数翻倍逼近，商累加 2 的幂。溢出边界是核心：MIN/-1 溢出，用 long 防中间溢出。用绝对值 + 符号处理。

示例代码

int divide(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; // 溢出
    long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
    long q = 0;
    while (a >= b) {
        long d = b, cnt = 1;
        while (d << 1 <= a) { d <<= 1; cnt <<= 1; } // 除数翻倍
        a -= d; q += cnt;
    }
    return (dividend > 0) == (divisor > 0) ? (int) q : (int) -q;
}