一个后台系统有十种权限:读、写、评论、删除、发布、审核、导出、邀请、改配置、看报表。最初的设计是标准的关联表,一张表存「谁有哪些权限」,每次校验多一次查询。后来为了省掉这次查询,有人把十个权限压进了一个整数,第 i 位表示第 i 种权限在不在,一次查询就能拿到全部信息。这个改法在性能上确实干净,上线后被沿用到了整个账号体系。
第三天,客服转来一个问题:一个只读账号能把别人的文章改掉。日志里权限值明明是 1,也就是只有 READ 那一位。同一周还有反方向的故障,管理员点了删除按钮没有任何反应,接口返回 200,帖子还在。
判断权限的那行代码是整件事的中心:
if (perm | WRITE) {
allowEdit();
}
它写的是按位或。perm 是 1,WRITE 是 2,按位或得到 3,非零,在任何语言里都被当成真。于是只要这个字段有值,判断就通过,和用户到底有没有写权限完全无关。正确的写法是按位与:只有 perm 里真的带着 WRITE 那一位,结果才非零。
这篇从这两行代码往外扩:0 和 1 能组成什么样的代数,六个位运算符各自在做什么,为什么一个整数可以当集合用,以及什么时候该停手、换回一张表。
第 i 位表示第 i 种权限
位(bit)是二进制的一位,只能是 0 或 1。整数在内存里就是一排位,只是平时我们看的是它的十进制写法。把第 i 位当成一个布尔开关,这个整数就能同时存下几十个开关:第 0 位是读,第 1 位是写,第 2 位是评论,依此类推。这种用法叫位掩码(bitmask),那个只占一位的整数叫掩码,作用是「只挑出某几位」。
十种权限的常量应该这样定义,用移位而不是直接写十进制,这样位序一目了然:
READ, WRITE, COMMENT, DELETE = 1 << 0, 1 << 1, 1 << 2, 1 << 3
for name, bit in [("READ", READ), ("WRITE", WRITE), ("COMMENT", COMMENT), ("DELETE", DELETE)]:
print(name.ljust(8), bit, format(bit, "08b"))
本机 Python 3.15 的输出:
READ 1 00000001
WRITE 2 00000010
COMMENT 4 00000100
DELETE 8 00001000
一个整数在任何时刻都同时表达两件事:某一位对应的权限在不在。把十种权限合成一个值,就是把各自的位或起来。读加写加删除,值是 1 + 2 + 8 等于 11,二进制 00001011。反过来,拿到 11 之后想知道有没有删除权限,就看第 3 位是不是 1。整条链路上没有一次额外的查询,也没有一张额外的表。
代价从第一眼就存在:这个数字对人不可读。数据库里存着 1027,没人能心算出它代表哪几个权限,排查时必须写小工具把它拆回二进制。所以用位掩码的前提是团队愿意维护一份唯一的位序表。
0 和 1 上的代数,和命题逻辑是同一套
只看一位,0 和 1 上的运算只有三种:与、或、非。它们和上一篇的合取、析取、否定一一对应,只是换了符号:1 是真,0 是假,& 是且,| 是或,~ 是非。所以命题逻辑里的等值式,在这里全部成立,只是把命题符号换成了 0 和 1。
常用的定律列出来是这些:交换律 a & b = b & a、a | b = b | a;结合律 (a & b) & c = a & (b & c);分配律 a & (b | c) = (a & b) | (a & c);幂等律 a & a = a;吸收律 a | (a & b) = a;补余律 a | ~a = 1、a & ~a = 0;德摩根律 ~(a & b) = ~a | ~b、~(a | b) = ~a & ~b。
有一条和普通代数不一样,值得单独看:或对与也分配,a | (b & c) = (a | b) & (a | c)。在整数乘法里,加法对乘法不分配,a + b * c 不等于 (a + b) * (a + c)。布尔代数两条分配律都成立,这正是它比普通数系「整齐」的地方,也是化简条件时可以把括号随便展开的原因。
为什么逐位的定律能推广到整个整数?因为位运算的定义就是「每一位独立计算,互不干扰」。所以只要对单独一位成立的等式,对整排位就成立,逐位验算是完整的证明。这一点让位运算的化简可以放心地做,不需要考虑进位,也不需要担心溢出,那是有符号算术才有的问题。
反过来,一旦开始把整数当数值做加减乘除,位与位之间就不再独立,布尔代数的定律立刻失效。这也是为什么权限字段只能用位运算操作,不能用加减法凑。
六个运算符,用八位写一遍
位运算符一共六个:与 &、或 |、异或 ^、取反 ~、左移 <<、右移 >>。除了取反是一元的,其余五个都要两个操作数。下面用 13 和 11 这两个数演算,它们的八位形式分别是 00001101 和 00001011。
00001101 13
& 00001011 11
---------------
00001001 9
00001101 13
| 00001011 11
---------------
00001111 15
00001101 13
^ 00001011 11
---------------
00000110 6
与是「都 1 才 1」,所以第 0 位和第 3 位留下,结果是 9。或是「有 1 就 1」,结果的低四位全是 1,等于 15。异或是「不同才 1」,逐位比下来只有第 1、2 位不同,结果是 6。异或有一个很好用的性质:同一个值异或两次会还原,所以它常被用来做切换和简单校验。
取反是把每一位都翻转。左移把每一位往高位挪,右边补 0,等价于乘 2 的 k 次方;右移反过来,等价于除以 2 的 k 次方并向下取整。Python 跑出来的结果:
print("13 & 11 =", 13 & 11)
print("13 | 11 =", 13 | 11)
print("13 ^ 11 =", 13 ^ 11)
print("~13 =", ~13)
print("13 << 2 =", 13 << 2, "13 >> 2 =", 13 >> 2, "-13 >> 2 =", -13 >> 2)
print("format(13, '08b') =", format(13, "08b"))
print("FULL =", (1 << 8) - 1, "~13 & FULL =", ~13 & 0xFF, format(~13 & 0xFF, "08b"))
13 & 11 = 9
13 | 11 = 15
13 ^ 11 = 6
~13 = -14
13 << 2 = 52 13 >> 2 = 3 -13 >> 2 = -4
format(13, '08b') = 00001101
FULL = 255 ~13 & FULL = 242 11110010
注意 ~13 是 -14,不是 242。Python 的整数没有固定位宽,取反相当于在一段无限长的二进制上翻转,最高位变成符号位,结果就落进负数区间。想要的是「八位以内全部取反」,必须自己给出位宽:先算全集 FULL = (1 << 8) - 1 = 255,再写 ~13 & FULL,得到 242。这一步是整篇文章里最容易漏的地方。
右移对负数要小心。-13 >> 2 得到 -4 不是 -3。算术右移在补码上等价于「除以 4 再向下取整」,-3.25 取整到 -4,而直觉会截断成 -3。Python 里 -13 // 4 同样是 -4,C 和 Java 的整数除法则会截断,跨语言移植时经常在这里出事。
一个整数就是一个集合
把第 i 位看成「第 i 个元素在不在」,这个整数就成了一个集合的表示,术语叫位向量(bit vector)或特征向量。0 是空集,(1 << n) - 1 是前 n 个元素的全集。这个映射不是比喻,四个集合运算都能一一对上:并集是按位或,交集是按位与,差集是「与上补集」,补集是「取反再加掩码」。
差集写成 a & ~b 而不是 a & b。它的意思是:留下 a 里那些 b 没有的位。补集必须写成 ~a & FULL,因为没有全集就不知道「补」的范围,这和上一篇集合里「补集要先约定全集」是同一件事。
A = {0, 1, 2}
B = {2, 3}
def bits(s):
n = 0
for i in s:
n |= 1 << i
return n
def elems(n, width=6):
return {i for i in range(width) if n & (1 << i)}
print("A:", format(bits(A), "06b"), "| B:", format(bits(B), "06b"))
print("并集:", elems(bits(A) | bits(B)), A | B)
print("交集:", elems(bits(A) & bits(B)), A & B)
print("差集:", elems(bits(A) & ~bits(B)), A - B)
print("补集:", elems(~bits(A) & 0b111111), {0, 1, 2, 3, 4, 5} - A)
A: 000111 | B: 001100
并集: {0, 1, 2, 3} {0, 1, 2, 3}
交集: {2} {2}
差集: {0, 1} {0, 1}
补集: {3, 4, 5} {3, 4, 5}
四行输出全部一致,说明位运算和集合运算确实同构。这个同构关系解释了一个常见的性能技巧:判断「两个用户有没有共同好友」可以用位向量做一次与运算,结果非零就是有交集。前提是两个位向量用的是同一套编号,否则第 5 位在两个集合里指的不是同一个人,交集就毫无意义。
同构也解释了它的天花板:集合大小固定死在位宽里。一万个元素要一万位,约一千多字节,还能接受;一亿个元素就是 12MB 一个集合,做一次并集要扫 12MB,比哈希集合慢得多。所以位向量适合小而稠密的集合,比如权限、状态标记、星期几,不适合稀疏的大集合。
四种操作:has、add、remove、toggle
权限系统真正需要的只有四个动作:判断有没有、加一个、删一个、切换一个。每个动作对应一条位运算表达式,写错任意一条都会变成线上事故。
READ, WRITE, COMMENT, DELETE = 1 << 0, 1 << 1, 1 << 2, 1 << 3
ALL = (1 << 4) - 1
def has(perm, bit):
return (perm & bit) != 0
def add(perm, bit):
return perm | bit
def remove(perm, bit):
return perm & ~bit
def toggle(perm, bit):
return perm ^ bit
perm = READ
print("start:", perm, format(perm, "08b"))
print("has READ:", has(perm, READ), "| has WRITE:", has(perm, WRITE))
perm = add(perm, WRITE)
print("after add WRITE:", perm, format(perm, "08b"))
perm = add(perm, DELETE)
print("after add DELETE:", perm, format(perm, "08b"))
perm = remove(perm, WRITE)
print("after remove WRITE:", perm, format(perm, "08b"))
perm = toggle(perm, COMMENT)
print("after toggle COMMENT:", perm, format(perm, "08b"))
perm = toggle(perm, READ)
print("after toggle READ:", perm, format(perm, "08b"))
print("remove 不存在的位:", remove(perm, WRITE), format(remove(perm, WRITE), "08b"))
print("台面之外的位:", perm & ~ALL)
start: 1 00000001
has READ: True | has WRITE: False
after add WRITE: 3 00000011
after add DELETE: 11 00001011
after remove WRITE: 9 00001001
after toggle COMMENT: 13 00001101
after toggle READ: 12 00001100
remove 不存在的位: 12 00001100
台面之外的位: 0
判断为什么必须写 != 0 而不是 == 1:单个权限的掩码只占一位,结果确实是 1,但组合权限的掩码占多位,结果会是 1、2、4 的组合。写成 == 1 时,一个同时有 READ 和 WRITE 的用户检查 WRITE 会得到 3,判成假。所以统一写「结果非零」,语义是「至少有一个位命中」。
加权限用或,因为或是幂等的:已经有这一位,再或一次不变。这条性质让「重复添加」不会出问题,接口可以安全地重试。这也是或和加法的关键差别,加法会把重复的权限变成进位,直接污染高位。
删权限用 & ~bit,意思是「保留除这一位以外的所有位」。不能写成 perm - bit:如果用户本来没有这一位,减法会向高位借位,把一个更大的权限位减掉,结果莫名其妙。也不能写成 perm ^ bit:异或是切换,用户没有这一位时,删除操作反而把它加上了。上面输出里 remove 不存在的位 保持 12 不变,正是删除该有的行为。
切换用异或,适合「点一下开,再点一下关」的开关。但权限系统里很少需要切换,因为用户的操作意图是「给我这个权限」或「收回这个权限」,不是「翻转」。把切换和删除混用,就是那类「点了两次删除,权限又回来了」的怪问题。
还有一个更隐蔽的写法差异:检查组合权限时,(perm & combo) != 0 只保证「至少有一项」,(perm & combo) == combo 才保证「全都有」。前者适合「有任一权限就能进这个页面」,后者适合「必须同时具备读写才能提交」。跑一遍就看得很清楚:只读用户的 perm 是 1,检查读写组合时,非零判断为真,完整判断为假。
READ, WRITE = 1, 2
perm = READ
combo = READ | WRITE
print("perm & combo =", perm & combo, "| != 0:", (perm & combo) != 0, "| == combo:", (perm & combo) == combo)
perm & combo = 1 | != 0: True | == combo: False
取反必须配掩码,位宽必须写死
取反是最容易出事的一个,因为它依赖位宽,而多数语言把位宽藏了起来。Python 的整数没有固定宽度,~7 是 -8;C 的 int 通常是 32 位,有符号结果同样是 -8,按无符号解释却是 4294967288;Java 的 long 是 64 位,按无符号解释还要更长。有符号结果一致,是因为 -8 在所有位宽里都装得下;一旦按无符号位模式使用,位宽立刻显形。
处理办法只有一条:先定义全集,再把取反结果与全集相与。存进数据库之前、发给前端之前、拿去和别的权限比较之前,都要过这一步。少了掩码,这个字段可能出现负数,而负数在 JSON、URL 参数、某些数据库列类型里会继续变形状。
~perm 的结果。Python 里它是负数,C 的有符号整型是负数,JavaScript 里可能因为 32 位截断变成另一个负数。补集要么立刻与全集相与,要么根本不要存,改成「查的时候现算」。位宽本身也有上限。一个 64 位整数最多表达 64 个开关,这是硬边界。权限枚举超过 64 种时,继续往一个整数里塞就会撞墙:Java 的 long 只有 64 位,Python 虽然能自动扩展,但存进数据库的 BIGINT 又会截断。超过这个数量,正确做法是换结构:多个整数拼成一个位向量数组,或者干脆退回关联表,用「用户 ID + 权限 ID」两列存。
右移分两种。有符号右移把符号位一起搬,高位补的是符号位的值,所以 -8 >> 2 得到 -2,数值上是「除以 4 向下取整」。无符号右移高位一律补 0,JavaScript 写成 >>>,-8 >>> 2 得到 1073741822,因为 -8 的 32 位补码被当成了一个很大的正数。用无符号右移处理负数索引或者高位掩码,几乎一定会得到意外的大数。
console.log("1 << 40 =", 1 << 40);
console.log("1n << 40n =", 1n << 40n);
console.log("1 << 31 =", 1 << 31);
console.log("(1 << 31) >>> 0 =", (1 << 31) >>> 0);
console.log("-8 >> 2 =", -8 >> 2);
console.log("-8 >>> 2 =", -8 >>> 2);
console.log("~5 =", ~5);
1 << 40 = 256
1n << 40n = 1099511627776n
1 << 31 = -2147483648
(1 << 31) >>> 0 = 2147483648
-8 >> 2 = -2
-8 >>> 2 = 1073741822
~5 = -6
第一行是最值得记住的:JavaScript 的位运算按 32 位执行,移位数会先对 32 取模,所以 1 << 40 实际算的是 1 << 8,得到 256,而不是一万亿。第 31 位是符号位,1 << 31 直接变成最小负整数。要用到 32 位以上,只能换成 BigInt 并加 n 后缀,第二行才是正确结果。
还有一条跨越语言的坑:大整数经过 JSON 会掉精度。JavaScript 的数字是双精度浮点,安全整数上限是 2 的 53 次方减一。一个把第 53 位之后用上的权限值,经过 JSON.parse 之后末位就变了,后端算出来的权限和前端收到的不再是同一个数。
const raw = '{"perm": 9007199254740993}';
console.log("parsed:", JSON.parse(raw).perm);
console.log("safe max:", Number.MAX_SAFE_INTEGER);
parsed: 9007199254740992
safe max: 9007199254740991
输入里最后一位是 3,解析出来变成 2。这种错误不会抛异常,只会让权限判断在某几个高位上永远差一位。规避方式是把权限值当字符串传,或用 BigInt 序列化。
一张现象对照表
下面这些症状都来自同一套东西,区别只在错在哪一步。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 只读用户能编辑 | 判断写成 perm | bit,或的结果几乎恒为非零 | 把判断表达式改成 perm & bit,打印两边的值 |
| 删除权限删不掉 | 用 ^ 当删除,用户本来没有这一位时反而加上了 | 确认删除写的是 perm & ~bit,并对没有该位的用户重跑 |
| 权限字段变成负数 | 取反没配掩码,无限位或有符号补码把高位全翻成 1 | 存储前先 & FULL,检查列类型是有符号还是无符号 |
| 加了新权限后旧权限错乱 | 新权限的位和旧权限重叠,两个枚举用了同一个 i | 把所有 1 << i 打印出来,检查有没有重复值 |
| 前端判断和后端不一致 | JavaScript 位运算只有 32 位,移位数按 32 取模 | 检查是否用到第 31 位以上,必要时换 BigInt |
| 数据库读出的权限对不上 | 列是 32 位整型,代码却用了 1 << 40 | 对照列类型上限和最大位序号 |
| 接口返回的权限末位变了 | 数值超过 2 的 53 次方,JSON 解析丢精度 | 改用字符串传输,或把权限压到安全整数范围内 |
| 两个人同时改权限,后改的覆盖先改的 | 读出来、改一位、写回去,中间没有原子性 | 检查是否用了事务、行锁或数据库的位运算更新 |
边界与代价
第一,可读性是持续成本。一个整数存十个开关,省下的是存储和查询,付出的是每次排查都要解码。团队里必须有唯一一份位序表,代码里的常量必须从同一处生成,不能各处手写十进制。更稳妥的做法是给调试接口留一个把整数拆成权限名的函数,出问题时先打印它。
第二,数据库会丢掉语义。存成整数之后,SQL 里没法直接写「查出所有有删除权限的用户」,只能用位运算表达式,而这类条件通常走不了索引,只能全表扫描。需要按权限筛选、统计、审计的场景,关联表反而更合适。位掩码适合「取出来就用」,不适合「按位查询」。
第三,64 位是硬天花板。超过 64 个枚举就得换结构,而且换的时候历史数据要迁移。用两个整数拼接看起来能撑到 128 位,但位序、越界、跨语言位宽的问题会成倍增加,通常不如直接换表。
第四,并发会丢更新。「读出来、或上一位、写回去」这三步不是原子的,两个管理员同时改权限,后写的会覆盖先写的。要么放在事务里加行锁,要么用数据库支持的原子位运算更新,要么用版本号做乐观锁。这类问题在测试环境几乎复现不出来。
第五,位含义不能随便改。某个位被赋予新含义后,历史数据里的这一位就全部变成新语义,旧记录没有任何标记能区分。要改只能加新位、保留旧位,或者做一次带版本号的数据迁移。
小结与练习
主线三句:布尔代数就是 0 和 1 上的与或非,定律和命题逻辑完全对应,逐位独立让这些定律可以整排使用;六个位运算符里,与用来判断和求交,或用来合并和添加,异或用来切换,取反必须配掩码;一个整数按位看就是集合,并交差补对应或与、与、与补,四种权限操作各有一条唯一正确的表达式。
当天可以自己验证的练习:
- 定义四个权限常量,打印各自的二进制;构造一个只有 READ 的 perm,分别求
perm | WRITE和perm & WRITE,解释为什么前者在 if 里恒为真。 - 写 has、add、remove、toggle 四个函数,对同一个 perm 连续操作,验证 remove 对不存在的位是幂等的,而 toggle 会把不存在的位加上。
- 用六个元素的两个集合,分别用整数位和 Python 的 set 求并、交、差、补,逐行比较结果是否一致;再把元素个数扩到一百,估算位向量占多少字节。
- 在 Node 里跑
1 << 31、1 << 32、1 << 40和1n << 40n,再用JSON.parse读一个 9007199254740993,解释两处差异分别来自位宽和浮点精度。 - 给十种权限排好位序,算出全集 FULL,写出「删除某权限」的表达式并加上掩码;最后用
format(perm, "010b")打印,确认每一位和权限名的对应关系。
下一篇讲图论基础。位掩码在图里出现得非常频繁:邻接矩阵的每一行可以压成一个整数,判断两个点是否相邻就是一次与运算;遍历时用来记录「访问过哪些点」的 visited 集合,也常是一个整数或一组位向量,标记和去重都变成了或运算。集合、逻辑、位运算这三篇铺垫的东西,会在图算法里同时出现。