位运算：原理、技巧与经典题型

为什么用位运算？

位运算直接操作整数的二进制表示，不需要额外内存、运算速度极快（CPU 单条指令完成）。在算法中，它常用于：

• 空间压缩：用一个 int 的 32 位表示 32 个布尔值
• 数学技巧：乘除 2 的幂次、奇偶判断
• XOR 消除：对称性消除重复元素
• 子集枚举：用位掩码遍历所有子集

基础运算速查

Java 特别注意：

• >> 是算术右移（正数高位补 0，负数高位补 1）
• >>> 是逻辑右移（高位始终补 0），常用于处理负数的位操作

最常用的位技巧

// ========== 检测 ==========
(n & 1) == 1           // 判断奇数
(n >> k) & 1           // 取第 k 位的值（0 或 1）
(n & (1 << k)) != 0   // 第 k 位是否为 1（两种写法）

// ========== 修改位 ==========
n | (1 << k)           // 将第 k 位置 1
n & ~(1 << k)          // 将第 k 位清 0
n ^ (1 << k)           // 翻转第 k 位

// ========== Brian Kernighan 技巧 ==========
n & (n - 1)            // 消去最低位的 1（n=1100 → 1000）
n & (-n)               // 取出最低位的 1（n=1100 → 0100）
                       // -n = ~n + 1（补码），所以 n & (-n) = lowbit

// ========== 其他 ==========
a ^ a == 0             // 自身异或为 0
a ^ 0 == a             // 与 0 异或不变
Integer.bitCount(n)    // n 的二进制中 1 的个数（内置方法）

为什么 n & (n-1) 能消去最低位的 1？

n 的最低位 1 设在第 k 位：

n   = ...1 0000  (第k位为1，后面全是0)
n-1 = ...0 1111  (第k位变0，后面全变1)
n & (n-1) = ...0 0000  ← 第k位及以下全清零

XOR 三定律与应用

a ^ a = 0     （自身异或归零）
a ^ 0 = a     （与0异或不变）
a ^ b = b ^ a （交换律）
(a ^ b) ^ c = a ^ (b ^ c) （结合律）

只出现一次的数 I（LeetCode 136）

数组中除一个数只出现一次，其余都出现两次，找出那个数：

int singleNumber(int[] nums) {
    int res = 0;
    for (int n : nums) res ^= n;
    // 出现两次的：a ^ a = 0，自动抵消
    // 最终只剩那个出现一次的数
    return res;
}

只出现一次的数 III（LeetCode 260）

两个数各自只出现一次，其余都出现两次：

int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int n : nums) xor ^= n;  // xor = a ^ b（非0，因为a≠b）
    
    // 找 a 和 b 在哪一位不同（取 a^b 最低位的 1）
    int diff = xor & (-xor);
    
    // 按该位是否为 1 分成两组，各自 XOR，分别得到 a 和 b
    int a = 0;
    for (int n : nums)
        if ((n & diff) != 0) a ^= n;
    
    return new int[]{a, xor ^ a};
}

原理：diff 是 a 和 b 不同的某一位。在这一位，a 和 b 一个为 0、一个为 1，所以可以把所有数分成两组，每组内 XOR 消去成对的数，得到 a 或 b。

统计 1 的个数（汉明重量）

方法 1：Brian Kernighan（推荐）

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);  // 每次消去最低位的 1
        count++;
    }
    return count;
}

时间复杂度：O(k)，k 是 1 的个数（通常 << 32）

方法 2：DP 批量计算（LeetCode 338）

求 0..n 中每个数的 1 的个数：

int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // i >> 1 是 i 去掉最低位，1 的个数已知
        // (i & 1) 是最低位是否为 1
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

原理：dp[4] = dp[0b100] = dp[0b010] + 0 = dp[2] + 0，即"右移一位的结果"+"最低位"。

2 的幂检测

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
    // 2的幂的二进制只有一个1，消去最低1后为0
}

boolean isPowerOfFour(int n) {
    // 2的幂 + 该唯一的1在奇数位（0、2、4...位）
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xAAAAAAAA) == 0;
    // 0xAAAAAAAA = 1010...1010 (偶数位全为1)，
    // 4的幂的那个1必须在偶数位（不能被0xAAAAAAAA覆盖）
}

格雷码（LeetCode 89）

n 位格雷码：相邻数字只有一位二进制不同。第 i 个格雷码 = i ^ (i >> 1)。

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

验证（n=3）：

i: 000 001 010 011 100 101 110 111
G: 000 001 011 010 110 111 101 100
     ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
     (每相邻两个只差1位，且最后和第一个也只差1位)

小结：常见场景对应技巧