S03-X06 · 位运算技巧：从奇偶判断到状态压缩

一个 int 有 32 个格子，一个 long 有 64 个。业务系统里的开关、权限、标签、已访问节点，数量通常到不了 64 个，但代码里给每一项配一个 boolean 字段的做法仍然到处都是。位运算不是炫技，是把 N 个布尔值压进一个整数、把集合判定压进一条 CPU 指令的基本功。难点从来不在算式，而在两处隐含规则：补码的符号位，以及移位距离按位宽取模。

1. 七个运算符的语义

运算符	名称	对 `int` 的行为	典型用途
`&`	与	两位都为 1 才得 1	取位、清位、掩码过滤
`\|`	或	有一位为 1 就得 1	置位、合并集合
`^`	异或	两位不同才得 1	翻转位、成对对消
`~`	取反	逐位翻转，含符号位	构造清除掩码
`<<`	左移	低位补 0，高位丢弃	乘 2 的幂、构造掩码
`>>`	算术右移	高位补符号位	有符号除法近似
`>>>`	逻辑右移	高位一律补 0	无符号视角、取高位

Java 没有无符号整型，整数一律补码，所以右移必须分两套：>> 保持符号，>>> 把结果当无符号数看。

int x = -8;                       // 补码 ...11111000
System.out.println(x >> 1);        // -4，高位补 1
System.out.println(x >>> 1);       // 2147483644，高位补 0
System.out.println(~5);            // -6，恒等于 -5 - 1
System.out.println(~x == -x - 1);  // true，对任意 int 成立

~x == -x - 1 值得记住：取反不是取相反数，两者差 1。所有"清位"写法 x & ~mask 能成立，靠的就是取反后目标位恰为 0、其余位不动。

一句话：>> 管符号，>>> 管干净，~ 永远比相反数小 1。

2. 常用技巧集中展示

下面七条覆盖了日常九成场景。全部按 JDK 17 核对过行为。

int x = 12;                        // 二进制 1100

// 1. 判奇偶：比 x % 2 更直接，且负数也正确
boolean odd = (x & 1) == 1;        // 12 & 1 == 0 -> false

// 2. 取最低位的 1（lowbit）：1100 -> 0100
int low = x & -x;                  // 4
//    对 Integer.MIN_VALUE 返回它自身，因为 -x 溢出仍是原值

// 3. 清掉最低位的 1：1100 -> 1000
int cleared = x & (x - 1);         // 8
//    反复执行可数 1 的个数，但应直接用 Integer.bitCount

// 4. 判 2 的幂：只有一位为 1，必须显式排除 0 和负数
boolean powerOfTwo = x > 0 && (x & (x - 1)) == 0;

// 5. 取模 2^n：仅对非负有效，负数会得到错误结果
int n = 4;
int mod = x & ((1 << n) - 1);      // 等价 x % 16，但更快

// 6. 统计置位个数与位置，优先用 JDK 方法而不是手写循环
int ones = Integer.bitCount(x);                  // 2
int trailing = Integer.numberOfTrailingZeros(x);  // 2，最低位 1 的下标

x & -x 与 x & (x - 1) 是一对：前者只留最低位的 1，后者只去最低位的 1。Fenwick 树的 lowbit 跳转用前者，判 2 的幂用后者。

Integer.toBinaryString 是调试时最该用的方法：把掩码原样打印，比对着十进制猜快得多。

3. `^` 的三个经典用法

异或的核心性质只有三条：a ^ a == 0、a ^ 0 == a、满足交换律与结合律，三条直接推出三个用法。

// 1. 交换两数，不需要临时变量
int a = 3, b = 5;
a ^= b; b ^= a; a ^= b;            // a=5, b=3

// 2. 找出只出现一次的数，其余元素都出现两次
int single = 0;
for (int v : nums) single ^= v;    // 成对的自动对消，剩下那个

// 3. 找缺失数字：1..n 全异或，再与数组异或
int missing = 0;
for (int i = 1; i <= n; i++) missing ^= i;
for (int v : nums) missing ^= v;

// 4. 不用中间变量翻转某一位
flag ^= MASK_BIT;                  // 0 变 1，1 变 0

第一条有个必须记住的坑：两个操作数指向同一位置时，三步交换会把该位置清零。写成 nums[i] ^= nums[j] 且 i == j，结果直接变 0。只有确认下标不同才可以这么写。

第二条的变体是"只出现一次的两个数"：全体异或得 x ^ y，取 lowbit = diff & -diff 按该位分两组，各自异或即得两个答案。

一句话：异或是对消运算，前提是元素个数为偶数；一旦有第三个同值元素，所有结论作废。

4. 位图与状态压缩

一个整数就是定长位向量。把第 k 位当作第 k 号元素，集合操作全部变成算术。

操作	表达式	说明
加入 k	`mask \|= 1 << k`	或运算置位
删除 k	`mask &= ~(1 << k)`	与取反掩码清位
判断 k	`(mask & (1 << k)) != 0`	不能写成 `== 1`
翻转 k	`mask ^= 1 << k`	异或翻转
集合大小	`Integer.bitCount(mask)`	无需遍历
全集	`(1 << n) - 1`	n 个元素全置位

int mask = 0;
mask |= 1 << 3;                          // 加入 3
boolean has = (mask & (1 << 3)) != 0;    // 查询 3
mask &= ~(1 << 3);                       // 删除 3
int size = Integer.bitCount(mask);       // 集合大小

// 枚举 mask 的全部子集，包含空集时把条件改成 s >= 0 并单独防重
for (int s = mask; s > 0; s = (s - 1) & mask) {
    // s 是 mask 的一个子集，按位递减不会产生重复
}

(s - 1) & mask 是状态压缩 DP 的标准骨架：在当前子集里去掉一个元素再与全集取交，按位序枚举、不重复。枚举全部子集的总代价是 3 的 n 次方，n 稍大就不可接受。

TSP 式 DP 是同一思想的另一面：dp[mask][i] 里 mask 表示已访问城市集合，i 表示当前停在哪个城市，转移写作 dp[mask | (1 << j)][j]。状态数是 2 的 n 次方乘 n，n 到 20 上下这张表就很难放进常规堆，所以状态压缩天然只适用于小 n。

5. `EnumSet` 与 `BitSet` 的选型

JDK 已经把位向量封装好了，但两个类的实现路径完全不同。

维度	`EnumSet`	`BitSet`
元素类型	只能是单个枚举类型	任意非负 `int` 下标
元素上限	枚举常量个数	无固定上限，按需扩容
内部结构	元素 ≤ 64 用 `RegularEnumSet`（单个 `long`）；> 64 用 `JumboEnumSet`（`long[]`）	始终是 `long[]`
遍历方式	`for (E e : set)`	`nextSetBit` 逐个跳
稀疏场景	不适用	下标稀疏时仍有扩容成本
序列化/落库	不适合，需转掩码	不适合，需转字节数组

enum Perm { READ, WRITE, EXEC, ADMIN }

EnumSet<Perm> set = EnumSet.of(Perm.READ, Perm.WRITE);
set.add(Perm.EXEC);
boolean ok = set.contains(Perm.ADMIN);     // false
EnumSet<Perm> all = EnumSet.allOf(Perm.class);
EnumSet<Perm> none = EnumSet.noneOf(Perm.class);

BitSet bits = new BitSet();
bits.set(3);
bits.set(70);
bits.clear(3);
bits.flip(5);
// 按升序跳着遍历，比 for 全扫快得多
for (int i = bits.nextSetBit(0); i >= 0; i = bits.nextSetBit(i + 1)) {
    System.out.println(i);
}
long count = bits.cardinality();           // 置位总数
int last = bits.length();                  // 最高置位下标 + 1

选型结论：枚举集合固定用 EnumSet，它是 JDK 里最紧凑的 Set 实现；下标是任意整数、要动态扩容用 BitSet；要落库、走 RPC 的，用自己维护的 int/long 掩码。

EnumSet 没有公开构造器，只能走 of、allOf、noneOf、complementOf 这些静态工厂——它需要在运行时按枚举常量个数决定用哪个实现。

6. 权限位设计：三种方案的取舍

方案	存储	查询成本	扩展性	适用
位掩码	一个 `INT` 列	一次与运算	加一位即加一个常量	权限项固定、数量 < 31
布尔字段	每项一列	读整行	加一项要改表结构	项少且需要独立索引/统计
集合字段（关联表）	子表多行	需要 join	加一项只加数据	项多、需要审计与动态配置

public final class PermMask {
    public static final int READ  = 1 << 0;   // 1
    public static final int WRITE = 1 << 1;   // 2
    public static final int EXEC  = 1 << 2;   // 4
    public static final int ADMIN = 1 << 3;   // 8
    public static final int ALL   = (1 << 4) - 1;  // 15

    // 授予：或运算
    static int grant(int mask, int bits) { return mask | bits; }

    // 收回：先取反再与，不能写成 mask ^ bits
    static int revoke(int mask, int bits) { return mask & ~bits; }

    // 校验：必须 != 0，因为结果可能等于该位本身
    static boolean has(int mask, int bit) { return (mask & bit) != 0; }

    // 校验全部具备
    static boolean hasAll(int mask, int bits) { return (mask & bits) == bits; }
}

revoke 那行是本节的要害：用异或收回权限，只会翻转当前状态——本来没有这位的账号，收回操作反而把它打开了。收回永远用 & ~bits。

落库时掩码用 INT UNSIGNED 或 BIGINT。MySQL 本身有 SET 类型，按官方文档其成员上限为 64 个、内部按位存储、查询用 FIND_IN_SET，但它的成员序位由建表定义决定，跨库迁移和代码常量之间很容易错位，业务权限更推荐自己维护掩码。

一句话：位掩码适合"读多写少、项固定"的权限，一旦需要按单项查询或动态审计，集合字段才是对的。

7. 移位边界：距离按位宽取模

Java 规定移位距离按左操作数位宽取模：int 取 & 31，long 取 & 63。这不是溢出保护，是语言规范。

System.out.println(1 << 32);      // 1，32 & 31 == 0，等于不移
System.out.println(1L << 64);     // 1，64 & 63 == 0，同样等于不移
System.out.println(1 << 33);      // 2，33 & 31 == 1
System.out.println(1 << -1);      // -2147483648，-1 & 31 == 31

System.out.println(1 << 31);      // -2147483648，第 31 位是符号位
System.out.println(1L << 31);     // 2147483648，long 里它是正数
System.out.println(1L << 63);     // -9223372036854775808，long 的符号位

两个直接后果：

用 1 << 31 当掩码，得到的是负数，mask > 0 这类判断会全线失效。掩码常量如果可能触及第 31 位，一律写 1L << 31 并把掩码变量声明成 long。
循环里写 1 << i 且 i 可能达到 32 以上时，实际生效的是 i & 31，表现为"移位绕着圈走"。需要超过 31 位就直接换 long 或 BitSet。

Long.numberOfTrailingZeros、Long.bitCount 这些方法的入参是 long，配合 1L << k 使用才不会在前面就丢掉高位。

8. 排错

现象	原因	处理
`x & (n - 1)` 对负数得到错值	掩码取模只对非负成立，补码高位的 1 被保留	改用 `Math.floorMod`，或在取模前确认非负
权限校验恒为真	写成 `(mask & bit) == 1`，结果实际是 `bit` 的值	改成 `!= 0`
收回权限后反而多了权限	用 `^` 代替 `& ~bit`	收回统一用 `mask & ~bits`
掩码常量出现负数	`1 << 31` 落到符号位	改 `1L << 31`，掩码用 `long`
移位结果"绕圈"	距离按 `& 31` / `& 63` 取模	超过位宽就换更宽的整型
`a ^= b; b ^= a; a ^= b` 把值清零	两个操作数是同一变量/同一数组下标	加 `if (i != j)`，或直接用临时变量

还有一条纯粹是认知问题：Integer 的 -128..127 缓存、Long 的缓存，与位运算毫无关系。看到"位运算省内存"就联想到装箱缓存，是两件不同的事；位运算省的是字段宽度与对象头，缓存省的是对象分配次数。

9. 边界

场景	更合适的做法	理由
开关数量会持续增长且需要独立查询	关联表 / 布尔列	掩码加位要动代码常量，改表更安全
需要"第几位置位"的语义化遍历	`BitSet.nextSetBit`	手写循环要自己处理跳位
元素是枚举且数量固定	`EnumSet`	内部就是一个 `long`，语义与性能兼得
稀疏大下标集合（如用户 ID）	`BitSet` 或分片位图	单个位图在极端稀疏时浪费扩容内存
跨语言/跨库传输	显式约定掩码表	位序必须写进文档，否则必然错位
状态压缩 DP	只在 n 较小时使用	状态数是指数级，没有通用解

一句话：位运算解决的是"宽度"问题，不是"规模"问题；元素一多、语义一复杂，就该换数据结构。

10. 自测

x & (x - 1) == 0 能判定 2 的幂吗？还需要补什么条件？
-8 >> 1 与 -8 >>> 1 的结果分别是多少，差异来自哪一位？
用 mask ^= bit 收回权限，会在什么情况下出错？
1 << 32 在 Java 里等于几？依据是哪条语言规范？
一个枚举有 80 个常量，EnumSet 会用哪种内部实现？
为什么状态压缩 DP 的 dp[mask][i] 表在 n 稍大时就放不下？