专题 14位运算

14.1位运算的本质：直接操作二进制

要理解位运算，先得想清楚「计算机里的整数到底长什么样」。整数在内存里是按二进制补码存储的——比如十进制的 12，在 32 位里就是 ...00001100，从左到右是「第 31 位、第 30 位……第 1 位、第 0 位」。 我们平时写的 a + b、a * 2，CPU 要先做一串算数逻辑；而位运算 a & b、a >> 1 是直接对这串 0/1 逐位操作的——它是离硬件最近的一层操作，所以又快又省。

为什么位运算快

「右移一位」在电路上就是把那串比特往右挪一格，一个时钟周期搞定；而「除以 2」在软件层面要经历除法器的一系列步骤，慢得多。同理，「判断奇偶」用 n & 1 取末位，比 n % 2 取模快——取模本质是做除法。 当然，现代 JVM 很聪明，很多时候会把 n % 2、n / 2 自动优化成位运算。但位运算真正的价值不止是快，更是能表达「逐位思维」：当你需要「数一个数里有几个 1」「把成对的消掉」「把某个开关拨到开 / 关」时，位运算是最自然的语言。

什么时候该想到位运算

看到下面这些「信号」，别急着上哈希和循环，先想想能不能用位来解决：

• 「成对出现，只有一个落单」——所有数都出现偶数次、或都成对，只有一个特殊。异或（相同为 0、不同为 1）天生擅长「抵消成对」，见 14.4、14.6。
• 「判断是不是 2 的幂 / 4 的幂」——2 的幂的二进制只有一个 1，这个结构用一次 n & (n-1) 就能识别，见 14.5。
• 「状态开关 / 多标志位」——用一个数的不同位表示多个布尔状态（比如第 0 位表示「是否访问过」），用 | 打开、& 读取、^ 翻转。
• 「快速除 2 / 乘 2 / 取末位」——移位比乘除高效，且能避免浮点。
• 「统计某些二进制特征」——如「有几个 1」「最低位的 1 在哪」，只能用位运算高效做，见 14.3 与 14.2 的 n & -n。

14.2六个常用技巧

位运算的工具箱不大，但高频的就这几个。下面这张表是整章的「字典」，建议背下来——后面每一题都是其中一个或两个的组合。

下面用 12（二进制 1100） 把每个技巧都跑一遍，建立肌肉记忆。注意这里 12 是 4 位视角，高位全是 0，我们只看低 4 位。

① n & 1 判奇偶

12 的二进制:  1100
            & 0001   (即 1)
            ------
              0000   → 结果为 0，说明 12 是偶数
原理：末位是 0 → 偶数；末位是 1 → 奇数

② n >> 1 除 2

12 的二进制:  1100
右移一位:     0110   → 即十进制的 6，正好是 12/2
注意：这是「向下取整」的除法，13 >> 1 = 6（不是 6.5）

③ n & (n - 1) 去最低位 1

12  = 1100
12-1= 1011   （减 1 把最低位的 1 变成 0，其右边的 0 全翻成 1）
12 & (12-1):
  1100
& 1011
  ------
  1000   → 8，原来最右边的那个 1 被抹掉了

④ n & (-n) 取最低位 1

12  = ...00001100
-n  = 补码(~n + 1) = ...11110100   （取反加一）
12 & -12:
  00001100
& 11110100
  --------
  00000100   → 4，恰好是「最低位那个 1」所代表的值

为什么 n & -n 能「掏出」最低位的 1？补码 -n = ~n + 1 有个性质：~n 把 n 的所有位取反，于是 n 里最低位的 1 在 ~n 里是 0，且其右边全是 1；加 1 之后，右边那些 1 又进位变回 0，最低位 1 的位置变成 1。所以 ~n+1 和 n 只有在「最低位 1」那一位同为 1，其余位都相反，& 一下就只留下它。

⑤ 异或三性质

a ^ a = 0      （相同的两个数异或，每一位都相同 → 全 0）
a ^ 0 = a      （和 0 异或，原样不变）
a ^ b = b ^ a  （交换律；还有结合律 a^(b^c)=(a^b)^c）
直觉：异或就是「无进位的加法」，相同抵消、不同保留

⑥ 判 2 的幂

8  = 1000  → 8 & 7  = 1000 & 0111 = 0000 → 是 2 的幂
6  = 0110  → 6 & 5  = 0110 & 0101 = 0100 ≠ 0 → 不是 2 的幂
原理：2 的幂的二进制「恰好只有一个 1」，而 n-1 会把那一个 1 变 0、右边全变 1，
      两者 & 起来所有位都是 0

14.3位 1 的个数（简单，力扣 191）

简单 核心：n & (n-1) 每次消一个 1，消几次就有几个 1

题意：给定一个无符号 32 位整数 n，返回其二进制表示中 1 的个数（也叫「汉明重量 / Hamming weight」）。 例如 n = 11（二进制 1011，有 3 个 1），返回 3；n = 128（二进制 10000000，1 个 1），返回 1。

思路推导：从逐位检查到「消 1 计数」

暴力法：不断对 n 取模 2、再除以 2，统计末位为 1 的次数。即 while (n > 0) { if (n % 2 == 1) cnt++; n /= 2; }。 这要循环「二进制位数」次（最多 32 次），可行但不是最优——因为它把每一位（包括大量的 0）都检查了一遍。

关键观察（优化）：我们其实只关心 1 在哪。14.2 学了 n & (n-1) 能「抹掉最低位的那个 1」。那我们何不每消掉一个 1 就计一次数？这样循环次数只等于「1 的个数」，n 里 0 再多也不影响。

为什么 n & (n-1) 每次恰好消掉一个 1？把 n 写成「...a1000」的形式，其中 a 是更左边的位，右边最低的 1 后面跟若干 0。减 1 时：最低位的 1 变成 0，它右边的所有 0 全部借位变成 1，得到「...a0111」。两者做 &：

n    = ...a 1 0 0 0
n-1  = ...a 0 1 1 1
n&(n-1) = ...a 0 0 0 0   ← 最低位那个 1 被抹掉了，左边 a 原样保留

可见每次 n = n & (n-1)，n 里就少一个 1，直到 n 变成 0（1 全消完）。循环体执行几次，就有几个 1。这正是「只数 1、跳过 0」的精髓。

参考代码

public class Solution {
    // 统计无符号整数 n 的二进制中 1 的个数
    public int hammingWeight(int n) {
        int cnt = 0;                 // 记录 1 的个数
        while (n != 0) {             // 只要还有 1 没消完就继续
            n = n & (n - 1);         // 抹掉最低位的那一个 1
            cnt++;                   // 每抹掉一个，计数 +1
        }
        return cnt;                  // n 归零时，cnt 就是 1 的总个数
    }
}

复杂度：时间 O(k)，k 是 n 中 1 的个数，最多 32 次；空间 O(1)。 对比暴力法的「固定 32 次」，当 n 中 1 很少时（比如 1000...000）本方法只循环 1 次，差距明显。本质上我们不再浪费时间去数那些 0。

14.4只出现一次的数字（简单，力扣 136）

简单 核心：异或三性质，成对的数互相抵消，只剩落单的

题意：给定一个非空整数数组，除了某一个元素只出现一次外，其余每个元素都恰好出现两次，找出那个只出现一次的元素。要求线性时间、且只用 O(1) 额外空间。 例如 nums = [4, 1, 2, 1, 2]，只有 4 落单，返回 4；nums = [2, 2, 1] 返回 1。

思路推导：从哈希到异或

暴力 / 常规思路：用哈希表统计每个数出现次数，扫一遍找到次数为 1 的。时间 O(n) 没问题，但空间 O(n)——题目明确要求 O(1) 空间，哈希不行。 或者用排序，相同数会挨在一起再扫描，时间 O(n log n)、空间 O(1)，但没利用到「恰好出现两次」这个强条件。

关键观察：「每个数都出现两次，只有一个出现一次」——这正是 14.2 里异或三性质的完美用场：

• a ^ a = 0：两个相同的数异或，直接变成 0，相当于「成对的互相抵消」。
• a ^ 0 = a：0 和任何数异或，原数不变，相当于「落单的保留下来」。
• 交换律 / 结合律：异或的顺序不影响结果，所以谁先谁后抵消都行。

于是把所有数从头到尾异或一遍：成对的都变成 0，0 再和那个落单数异或，结果就是落单数本身。整个过程只用一个变量，空间 O(1)。

示例 nums = [4, 1, 2, 1, 2]：
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)     // 交换/结合，把相同的凑一起
= 4 ^ 0 ^ 0
= 4                          // 落单的 4 被保留

参考代码

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;                 // 初始为 0（a^0=a，0 不影响结果）
        for (int x : nums) {
            ans ^= x;                // 逐个异或：成对的抵消成 0，落单的留下来
        }
        return ans;                  // 最终剩下的就是只出现一次的数
    }
}

复杂度：时间 O(n)（一遍遍历）；空间 O(1)（只用了 ans 一个变量）。 这是「用位运算把空间压到极致」的经典案例——哈希要 O(n) 空间，异或只要 O(1)，而且思路比哈希更优雅。

14.52 的幂（简单，力扣 231）

简单 核心：2 的幂的二进制只有一个 1，用 n & (n-1) == 0 识别

题意：给定一个整数 n，判断它是否是 2 的幂（即存在整数 k 使 n = 2^k）。是返回 true，否则 false。 例如 n = 1（2⁰）返回 true，n = 16（2⁴）返回 true，n = 3、n = 0、n = -16 都返回 false。

思路推导：从循环除 2 到一次位与

暴力法：不断把 n 除以 2，看最后能否到 1 且没有余数；或枚举 1, 2, 4, 8... 比较。时间 O(log n)，还要处理负数和 0 的边界，写起来啰嗦。

关键观察：2 的幂在二进制里有极其显著的特征——它恰好只有一个 1。比如：

1  = 0001
2  = 0010
4  = 0100
8  = 1000
16 = 10000

而 14.2 学过：n & (n-1) 会「抹掉最低位的那个 1」。如果 n 本来就只有一个 1，抹掉之后就变成 0；如果 n 不止一个 1（比如 6 = 0110），抹掉最低位 1 后还剩别的 1，结果就不是 0。

8  = 1000,  8-1 = 0111,  8 & 7  = 0000  → 0，是 2 的幂
6  = 0110,  6-1 = 0101,  6 & 5  = 0100  → 非 0，不是 2 的幂

所以判断条件就是 (n & (n-1)) == 0。但还差一个关键补充：n 必须大于 0。因为 n = 0 时 0 & (-1) = 0 也会成立，可 0 不是 2 的幂；负数更不是。所以完整条件是 n > 0 && (n & (n-1)) == 0。

参考代码

class Solution {
    public boolean isPowerOfTwo(int n) {
        // 必须 n>0：排除 0 和负数（0 & (0-1) 也等于 0，会误判）
        // n & (n-1) == 0：保证二进制里「只有一个 1」
        return n > 0 && (n & (n - 1)) == 0;
    }
}

复杂度：时间 O(1)（就一次位与和一次比较）；空间 O(1)。 对比暴力除 2 的 O(log n)，这是降维打击——把「判断数学性质」直接翻译成「看一个位结构」，常数时间搞定。

14.6丢失的数字（简单，力扣 268）

简单 核心：异或法——下标与值一起异或，成对的抵消，剩缺失的

题意：给定一个包含 [0, n] 中 n 个数的数组 nums（长度为 n），[0, n] 这 n+1 个整数里恰好缺了一个，找出这个缺失的数。 例如 nums = [3, 0, 1]（n=3，本应有 0,1,2,3），缺 2，返回 2；nums = [0, 1] 缺 2，返回 2；nums = [9,6,4,2,3,5,7,0,1]（n=9）缺 8，返回 8。

思路推导：从求和到异或

方法一（求和法）：0 到 n 的总和公式 n*(n+1)/2，减去数组所有元素的和，差就是缺失值。时间 O(n)、空间 O(1)，很直观。但它有个隐患：当 n 较大时 n*(n+1)/2 会超过 int 范围导致溢出（虽然 268 题 n≤10⁴ 还安全，但这种写法换个更大的数据就翻车）。

方法二（异或法，更稳）：把「缺失」看成另一种「成对抵消」问题。如果 0~n 每个数都出现且数组也包含它们，那把所有「下标 i」和「nums[i] 的值」以及最后的 n 一起异或，会怎样？

技巧在于：正常的配对是「下标 i 配对数值 i」。数组里大多数数值都能和某个下标配对抵消；唯一和任何下标都配不上的，就是缺失的那个值。具体做法：

令 ans = 0
先 ans ^= n                      （把最大的那个数 n 放进去）
对 i 从 0 到 n-1：
    ans ^= i ^ nums[i]           （下标 i 和 它对应的数值 nums[i] 一起异或）
结束时，成对的都抵消为 0，剩下的就是缺失的数

为什么？数组有 n 个元素、下标 0~n-1；而完整集合是 0~n 共 n+1 个数。下标 0~n-1 这 n 个「位置」会和数组中 n 个值配对：数组中存在的每个值 v，都会在某个 i 处作为 nums[i] 出现，于是 i ^ nums[i] 里如果 v 恰好等于某个下标，就抵消了……更严谨地说：把所有下标 0..n-1、所有 nums[i]、以及 n 这 (n) + (n) + 1 个数全部异或，每个「在数组里出现的值」都和「它的某个下标」同值相消，最终只剩「没有下标跟它配对的值」——也就是缺失的那个数。配合 14.4 的 a^a=0, a^0=a，结果水落石出。

参考代码

class Solution {
    public int missingNumber(int[] nums) {
        int ans = nums.length;      // 先把 n（即 nums.length）放进 ans
        for (int i = 0; i < nums.length; i++) {
            ans ^= i;               // 异或下标 i
            ans ^= nums[i];         // 异或它对应的值 nums[i]
        }
        return ans;                 // 成对的抵消完，剩下缺失的数
    }
}

复杂度：时间 O(n)（一遍遍历）；空间 O(1)（只用 ans）。 相比求和法，异或不会溢出——它不累积大小，只做位翻转，这对大 n 尤其安全。这也是为什么很多官方题解更偏爱异或。

14.7本专题常见坑

14.8自测题