外观
25 - 位运算不是炫技:权限掩码、集合运算与状态压缩
前置阅读:21 - 动态规划的状态与转移。
本文中的状态压缩只改变表示方式;状态数量仍可能是指数级。
摘要
如果读、写、删除三种权限各用一个布尔值表示,就需要分别记录三个“有或没有”。位运算把这些状态放进整数的不同二进制位:每位用 1 表示有,用 0 表示没有。这样既能组合权限,也能表示一个小集合中选中了哪些元素。
下面先建立位与集合的对应关系,再解释权限操作、异或和位计数,最后讨论状态压缩与动态规划。使用这些方法时,要同时考虑整数位宽和状态数量。
1. 权限掩码
位掩码(bit mask,代码中常写作 mask)是用二进制位标记状态的整数。位编号从右向左、从 0 开始。约定第 0 位代表读、第 1 位代表写、第 2 位代表删除后,011 就表示“有读和写,没有删除”。以下二进制示意只展示低三位,实际 Java 整数还有更多位。
1 << i 表示把整数 1 向左移动 i 位,因此 1 << 0、1 << 1、1 << 2 分别得到 001、010、100。每种独立权限占一位,才能在组合时保留各自的信息。
按位运算对每个位置分别计算,不会把整个整数当作一个布尔值:
| 运算 | Java 符号 | 单个位的规则 | 集合含义 |
|---|---|---|---|
| AND(与) | & | 两边都是 1 才得 1 | 交集 |
| OR(或) | | | 至少一边是 1 就得 1 | 并集 |
| XOR(异或) | ^ | 两边不同得 1,相同得 0 | 只在一边出现的元素 |
| NOT(取反) | ~ | 0、1 互换 | 在整数位宽内翻转全部位 |
下面是 Java 类中的字段和方法片段,第 5 节给出完整类:
java
static final int READ = 1 << 0;
static final int WRITE = 1 << 1;
static final int DELETE = 1 << 2;
static int grant(int permissions, int permission) {
return permissions | permission;
}
static int revoke(int permissions, int permission) {
return permissions & ~permission;
}
static boolean has(int permissions, int permission) {
return (permissions & permission) == permission;
}grant 用 OR 把目标权限位置为 1,其他位保持原样,所以重复授权不会改变结果。revoke 先用 ~permission 把目标位变成 0、其余位变成 1,再用 AND 清除目标位,因而重复撤销也不会影响其他权限。
has 检查的是“是否拥有要求的全部权限”:AND 保留下来的位必须与 permission 完全相同。若只要求“至少拥有其中一种”,才判断 AND 结果是否非 0。当 permission == 0 时,当前 has 返回 true,因为没有任何待满足的权限位;调用方应明确这种空要求是否符合业务语义。
2. XOR 的性质
XOR 会把不同的位变成 1、相同的位变成 0。因此,一个整数与自身异或时所有位都抵消,与 0 异或时所有位都保持原样:
text
x ^ x = 0
x ^ 0 = x异或还满足交换律和结合律,因此把一组整数依次异或时,相同元素可以两两抵消,不要求它们在数组中相邻。如果一个元素出现一次、其余元素都恰好出现两次,最终就只剩那个单独出现的元素:
java
static int singleNumber(int[] values) {
int result = 0;
for (int value : values) result ^= value;
return result;
}这段解法依赖上述输入约束,不负责检查约束是否成立。若输入不符合约定,返回值只是全体元素的异或结果,不能据此断言找到了唯一元素;空数组会返回 0。
3. n & (n - 1)
这里的“最低位的一个 1”指最靠右的 1,不一定是第 0 位。以 n = 101100 为例,减一得到 101011:最靠右的 1 变为 0,它右侧的 0 变为 1,更高位不变。两者按位 AND 后得到 101000,恰好只清除了那个 1。
因此,每次执行 n & (n - 1) 都少一个 1,反复执行到 0 就能统计置位数量(即二进制表示中 1 的个数):
java
static int bitCount(int value) {
int count = 0;
while (value != 0) {
value &= value - 1;
count++;
}
return count;
}value == 0 时循环不执行,返回 0。这里统计的是 Java int 的 32 位表示中的 1,也包含负数的符号位;它不是只统计绝对值的二进制表示。生产代码通常使用 Integer.bitCount(),对 long 则使用 Long.bitCount()。
4. 状态压缩
状态压缩是把多个状态值放进更紧凑的表示中。对于集合 {A,B,C},固定 A、B、C 分别对应第 0、1、2 位,掩码 101 就表示选中 A、C。0 表示空集合,111 表示全集;检查元素是否选中,就是检查它对应的位是否为 1。
n 个元素各有选中、未选中两种可能,共有 2^n 个子集。当元素数量较小,例如不超过 20,可以用整数表示选中集合,遍历 0 .. (1 << n) - 1 枚举全部子集。压缩的是每个集合的表示,子集数量仍然是 2^n。
“不超过 20”只是常见数量级直觉,不是固定安全线。真正成本还取决于每个状态的转移数、内存布局、时间限制和是否需要保存前驱。例如 O(n²2^n) 在 n=20 时也可能过大。
5. 完整可运行示例:权限、位计数与子集枚举
以下类只依赖 Java 标准库,可保存为 BitOperationDemo.java,使用本地 JDK 编译运行。前文权限片段使用 int,这里改用 long 演示更大的固定宽度;子集枚举仍使用 int,并把元素数量限制在 20 以内。
java
/**
* 可运行示例:位运算不是炫技:权限掩码、集合运算与状态压缩。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class BitOperationDemo {
static final long READ = 1L << 0,
WRITE = 1L << 1,
DELETE = 1L << 2;
static long grant(long mask, long permission) {
// OR 只会把 permission 中的目标位设为 1,不影响其他已授权位。
return mask | permission;
}
static long revoke(long mask, long permission) {
// ~permission 把目标位变为 0,再用 AND 清除对应权限。
return mask & ~permission;
}
static boolean has(long mask, long permission) {
// 只有 permission 中要求的每一位都存在,AND 结果才等于 permission。
return (mask & permission) == permission;
}
static int countOnes(long value) {
int count = 0;
while (value != 0) {
// value-1 会翻转最低位 1 及其右侧,AND 后恰好清除该位。
value &= value - 1;
count++;
}
return count;
}
static void printSubsets(String[] values) {
if (values.length > 20) throw new IllegalArgumentException(
"too many states"
);
// n 个元素共有 2^n 个子集,每个 mask 唯一表示一个选择集合。
int subsetCount = 1 << values.length;
for (int mask = 0; mask < subsetCount; mask++) {
System.out.print("[");
for (int i = 0; i < values.length; i++) {
// 第 i 位为 1,表示当前子集包含 values[i]。
if ((mask & (1 << i)) != 0) {
System.out.print(values[i] + " ");
}
}
System.out.println("]");
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
long p = grant(0, READ | WRITE);
System.out.println(has(p, WRITE));
p = revoke(p, WRITE);
System.out.println(has(p, WRITE));
System.out.println(countOnes(0b101101));
printSubsets(new String[] { "A", "B", "C" });
}
}入口先授权读写,再撤销写权限,前三行的预期结果依次为 true、false、4;随后按掩码从 0 到 7 打印 {A,B,C} 的八个子集,从空集合开始,到全集结束。这些是按代码推导的结果,不是实测输出。入口演示了普通权限操作、位计数和三个元素的子集枚举,没有覆盖后文建议的全部边界输入。
5.1 手工推演权限掩码
假设 READ=001、WRITE=010、DELETE=100。表中的 101 只展示 ~WRITE 的低三位;实际取反会作用于整数的全部位:
| 操作 | 表达式 | 结果 |
|---|---|---|
| 授予读写 | 000 OR 011 | 011 |
| 检查写 | 011 AND 010 | 010,存在 |
| 撤销写 | 011 AND 101 | 001 |
| 检查删除 | 001 AND 100 | 000,不存在 |
例如判断“同时拥有读和写”,应比较 (mask & (READ | WRITE)) == (READ | WRITE)。若 mask 只有读权限,AND 结果是 001,虽然非 0,却不等于要求的 011。
5.2 子集枚举与状态 DP
动态规划(DP)保存子问题的结果,并通过状态转移得到更大子问题的结果。用 dp[mask] 表示某个已选集合的结果,是把集合编码为数组下标;如果后续决策还依赖其他信息,就必须把这些信息也加入状态,例如旅行商问题中的当前终点。仅有集合掩码不一定足以描述子问题。
对非零 mask,previous = mask & (mask - 1) 会删除最低置位所代表的元素。例如 101 变为 100,对应从 {A,C} 中删去 A。mask ^ previous 只剩被删除的那一位,Integer.numberOfTrailingZeros 返回它右侧连续 0 的个数,也就是元素下标;从 previous 转移回 mask 时,这又是新增元素的下标。mask == 0 时没有可删除元素,不能这样取得有效元素下标。
这种按位增删的操作可用于旅行商、任务分配等小规模集合状态 DP,但具体转移仍由问题定义决定。
5.3 复杂度与边界
- 权限增删查都是
O(1);统计 1 的循环次数是已置位个数,最坏O(64)。 - 枚举全部子集的输出本身就有
2^n份,若每个子集扫描 n 位,总时间O(n·2^n)。 long最多容纳 64 个标志,其中第 63 位是符号位但仍可作普通位使用;序列化、数据库查询和跨语言交互必须统一位宽及符号解释。- 位宽容量不等于枚举能力:能在
long中保存 64 个标志,并不意味着能遍历它们的全部组合。示例的 20 元素限制用于控制枚举规模,不是权限位数上限。
6. 状态压缩 DP 的设计方法
先定义子问题,再决定如何用位表示其中的集合。设计时依次确认:
- 每一位对应什么对象,编号在整个计算期间是否稳定;
mask表示已经选择、尚未选择,还是当前可用集合;- 转移是新增一位、删除一位,还是枚举子集;
- 状态数量与每个状态的转移成本是否可接受;
- 是否需要记录前驱,即当前最优结果来自哪个先前状态,以恢复具体方案。
除了逐个增删元素,有些转移需要从当前集合中选出一组元素。下面枚举的是给定 mask 的子掩码:它只能保留 mask 中已有的 1,不能包含集合之外的元素。该 Java 循环片段要求 mask 非负、不使用 int 符号位;这是 subset > 0 能正确判断非空的前提:
java
for (int subset = mask; subset > 0; subset = (subset - 1) & mask) {
// subset 是 mask 的一个非空子集
}每轮先减一,再用 & mask 清除集合之外的位,从而得到下一个更小的子掩码。例如 mask = 101 时,依次访问 101、100、001,得到 0 后退出;空子集不会进入循环,mask == 0 时循环也不会执行。若转移需要空子集,应另行处理。
若 mask 有 k 个置位,它有 2^k 个子集,枚举非空子集需要 2^k - 1 轮。对所有 n 位掩码再枚举子掩码,每个元素有三种归属:不在 mask 中、在 mask 中但不在子掩码中、在子掩码中。因此总枚举量可达到 O(3^n);转移内部若还有额外操作,也要计入成本。
7. 验证与版本边界
本节是 Java 整数边界说明与建议的验证方法:
int移位距离只使用低 5 位,long只使用低 6 位,因此越界移位不会按直觉得到0。例如1 << 32的实际移位距离为0;应在移位前检查位编号是否落在所用类型的范围内。1 << bit先按int计算,之后赋值给long也不会补回丢失的位;需要long时应从左操作数开始写成1L << bit。- 序列化到数据库或其他语言时统一有符号性和位宽;以字节形式传输时还要约定字节序,即多字节整数的排列顺序。
- 用普通集合
Set<Integer>作为小规模基线,对相同输入比较集合增删查和子集枚举结果,避免只检查整数值却漏掉元素映射错误。 - 覆盖空权限、组合权限、重复授权/撤销、最高位、负数掩码、空集合及元素数上限。
printSubsets的空数组会打印一个空子集,超过 20 个元素会抛出异常;数组本身为null不属于合法输入。 - 输出具体方案时,检查掩码位、前驱记录和业务对象编号始终对应同一对象;中途更换编号会使恢复出的方案失去原有含义。
8. 容易踩的坑
1 << 31设置int的符号位,结果为负数,但这一位仍可表示标志。判断位是否存在应使用按位检查,不能把“掩码大于0”当作“非空集合”的通用条件。>>是带符号右移,左侧补原符号位;>>>是无符号右移,左侧补0。负数参与右移时,两者的结果可能不同。- 位运算与比较混写而不加括号,难以阅读。
- 权限超过整数位数却未迁移存储结构。
9. 工程建议
位掩码适合编号稳定、规模有限的标志集合。为每一位定义具名常量,并封装增删查方法,可以避免业务代码到处出现含义不明的数字和位表达式。
需要替代结构时,应按用途选择:EnumSet 表示枚举值的集合,适合固定的具名选项;BitSet 表示可扩展的位集合,仍需维护位编号的含义;权限需要动态配置、按名称查询、审计或细粒度属性时,关系表或显式权限对象通常更清晰。标志频繁新增或超过固定整数位宽时,应重新评估表示方式,而不是继续增加移位距离。
10. 总结
位运算适合紧凑表达有限状态,但必须明确每一位的语义和整数边界。
- OR、AND 与取反可以实现标志的添加、判断和删除。
- XOR 技巧依赖严格输入约束,不能脱离条件套用。
- 状态压缩减少表示成本,不会自动降低搜索空间复杂度。
概率集合结构继续阅读Bloom Filter 与概率判断。