位运算、Bitmap 与状态压缩

第一次碰到“位运算、Bitmap 与状态压缩”，我以为把定义和代码记下来就算学会了。真正动手时才暴露出问题：位运算符我很早就见过，但很长时间只会做奇偶判断，碰到状态压缩和 Bitmap 时仍然不知道每一位该代表什么。这次重学我刻意放慢了速度，先看它为什么出现，再看规则怎样工作，最后才落到实现。

位运算适合处理开关、集合、奇偶、权限、状态压缩等问题。它看起来像技巧，但本质是用二进制位表示多个布尔状态。

位运算解决什么问题

图：一个整数的每一位可以表示一个元素是否被选中

常用位运算：

只出现一次的数字

异或有三个性质：

• a ^ a = 0
• a ^ 0 = a
• 异或满足交换律和结合律

所以一组数里只有一个数出现一次，其他都出现两次，可以这样做：

int singleNumber(int[] nums) {
    int ans = 0;
    for (int x : nums) {
        ans ^= x;
    }
    return ans;
}

统计二进制 1 的个数

int bitCount(int x) {
    int count = 0;
    while (x != 0) {
        x &= x - 1;
        count++;
    }
    return count;
}

x & (x - 1) 每次都会消掉最低位的 1，所以循环次数等于 1 的个数。

Bitmap：用位表示存在性

如果要记录大量整数是否出现过，boolean[] 已经比 HashSet 省空间，但 Bitmap 更省。

class Bitmap {
    private final long[] words;

    Bitmap(int maxValue) {
        this.words = new long[(maxValue + 64) / 64];
    }

    void add(int x) {
        words[x / 64] |= 1L << (x % 64);
    }

    boolean contains(int x) {
        return (words[x / 64] & (1L << (x % 64))) != 0;
    }
}

Bitmap 适合值域已知、非负整数、只需要判断存在性的场景。它不适合直接保存对象，也不适合值域特别稀疏的场景。

状态压缩 DP

当元素个数较小，比如 n <= 20，可以用一个整数表示子集。

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) == 0) {
            int next = mask | (1 << i);
            // 从 mask 转移到 next
        }
    }
}

状态压缩不是为了炫技，而是把集合状态变成数组下标，避免用复杂对象做 key。

Java 中的注意点

• int 左移超过 31 位容易出错，大集合用 long 或 BitSet。
• 有符号右移是 >>，无符号右移是 >>>。
• 判断第 i 位要加括号：(mask & (1 << i)) != 0。
• 位运算可读性较弱，工程代码要写清楚变量名和注释。

我的分析

位运算适合“状态数量不大，但组合很多”的问题。如果 n 很大，2^n 的状态压缩会直接爆炸。判断是否使用它，不是看会不会写位运算，而是看状态规模是否允许。

面试题

1. x & (x - 1) 为什么能删除最低位的 1？
2. Bitmap 和 HashSet 的空间差异在哪里？
3. Java 中 >> 和 >>> 有什么区别？
4. 状态压缩 DP 为什么通常要求 n 比较小？
5. 如何用位运算判断一个数是否是 2 的幂？