一、为什么要重新捡起“位运算”

• 千万级数据去重，HashSet 内存爆炸，位图却能把 1 字节当 8 个标志位用；
• 权限系统膨胀到上千个维度，位掩码一次按位与就能完成鉴权；
• 高频状态切换，位字段把 64 种状态塞进一个 64 位整数，省去大量分支判断；
• 随机算法、一致性哈希、布隆过滤器、HyperLogLog，核心都是“把比特当概率桶”。

二、基础招式：与、或、异或、非、左移、右移的“语义”

1. 按位与（&）
   语义：保留“共同 1”，其余变 0。用途：掩码提取、权限交集、奇偶判断、清除标志位。
2. 按位或（|）
   语义：只要“有 1 就置 1”。用途：设置标志位、合并权限、构造掩码。
3. 按位异或（^）
   语义：相同为 0，不同为 1。用途：.toggle 开关、无中间变量交换、简单校验、对称差集。
4. 按位非（~）
   语义：全体翻转。用途：生成“全 1”掩码、取反码、边界技巧。
5. 左移（<<）
   语义：低位补 0，等效乘以 2^n。用途：快速乘法、生成第 n 位掩码、位图索引。
6. 右移（>>）
   语义：高位补 0（逻辑）或补符号位（算术），等效除以 2^n。用途：快速除法、提取高字段、哈希打散。

三、业务场景：把“位”当“桶”当“锁”当“维度”

1. 位图去重
   1 字节 = 8 标志位，1MB 能表示 800 万个是否存在。千万级 UID 去重，内存从几百 MB 压缩到几 MB，缓存命中率直线上升。
2. 位掩码权限
   读=1<<0，写=1<<1，执行=1<<2；鉴权时一次按位与即可返回“是否同时具备多个权限”。维度扩展到 64 个权限，仍在一个 64 位整数里完成。
3. 位字段状态
   订单“已支付、已发货、已签收、已评价”四个布尔标志，可以塞进同一个字节；序列化时直接写整数，节省 JSON 字段长度，也避免“忘写某个标志”导致的逻辑漏洞。
4. 位索引分桶
   把用户 ID 的后 6 位当成桶索引，0-63 自然分桶；再做“位与”打散，能缓解热点，也能作为一致性哈希的虚拟节点标记。
5. 位运算随机
   线性同余、Xorshift、SplitMix 等高速随机算法，核心都是“移位+异或+加法”；位运算版比乘除取模快一个数量级，适合在 GPU 或 SIMD 里批量生成。

四、算法实战：七道经典场景从头到尾“手算”一遍

1. 只出现一次的数字
   数组里除一个数字外，其他都出现三次。用“位计数”思想：对每一位统计 1 的个数，模 3 后剩余的 1 就是目标数字的该位。时间复杂度 O(n)，空间 O(1)。
2. 区间合并
   区间端点用“起点异或 1”得到自然序号，把区间映射成位图里的连续 1，再按位扫描最左最右 0，即可得到合并后的区间列表。省去排序+遍历的冗余分支。
3. 最大异或对
   把所有整数按最高位到最低位插进“二进制 Trie”，走“与当前位相反”路径，即可得到最大异或值。Trie 的插入与查询都是位运算版，比字符串版更快。
4. 交替位序列
   判断一个整数是否呈现 101010… 或 010101… 的交替模式。先左移再异或，得到全 1 或全 0，再用“全 1 加 1 等于全 0”特性一次性判断。三行位运算即可返回布尔值。
5. 位图排序
   把待排序整数当作位图索引，出现则置 1，最后顺序输出 1 的位置。时间 O(n)，空间 O(最大元素/8)。缺点：去重+排序一体，无法处理负数或重复计数。
6. 布隆过滤器
   用三个或更多哈希函数，每个哈希值对应一位；插入时置 1，查询时做按位与。假阳性可控，内存远小于哈希表。位运算版哈希可用 Xorshift 加速。
7. HyperLogLog
   把哈希值的前若干位当“桶索引”，后若干位当“前导零计数”，用位运算提取字段；再用“最大前导零”估计基数。位运算提取比乘除取模快，且易于在 FPGA 里并行。

五、性能陷阱：当“位运算”反而变慢时

1. 过度拆分
   把 64 个布尔字段拆成 64 次位运算，序列化时再拼装，结果 JSON 体积没减多少，CPU 却多了 64 次移位，得不偿失。位运算适合“密集标志”，不适合“稀疏字段”。
2. 缓存不友好
   位图虽然内存小，但访问是“随机跳地址”，CPU 预取失效；解决办法是“分块+批处理”，一次处理 4KB 位图，再写回内存。
3. 假共享
   两个线程分别改两个相邻的 int，但落在同一缓存行，导致缓存行来回失效。把 int 拆成“一人一行”就能解决；位运算同样要遵守“缓存行对齐”原则。
4. 分支误判
   用位运算目的是“消除 if”，但有人在位运算外套一层 if，导致 CPU 分支预测失败，性能反而下降。正确写法是：让位运算结果直接参与后续计算，去掉分支。

六、高级技巧：当位运算遇见向量与并发

1. SIMD 位运算
   AVX2 提供 256 位向量寄存器，一次做 256 个位与/或/异或；GPU 的 warp 也能在 32 位整数上并行位运算。位图过滤、布隆过滤器、随机数生成都能向量版实现，吞吐量提升 8–32 倍。
2. 无锁位图
   用 compare_and_swap 对 32 位或 64 位位图做“原子置位”；多线程同时标记桶时，无需 mutex，也能保证不丢标记。
3. 位运算+哈希
   MurmurHash、CityHash 的核心是“移位+异或+乘法”，位运算版比取模更快；分桶时把“取模”换成“位与”能把除法变成与操作，随机访问变顺序访问，缓存命中率大增。
4. 位字段并发
   把 64 个状态塞到一个 64 位整数，用原子位运算做“并发置位/清除”，比 64 次单独 CAS 快得多；但注意“假共享”：两个线程改相邻位，仍可能落在同一缓存行。

七、调试法门：肉眼可见的“位”

1. 二进制打印
   自己写辅助函数，把整数按 4 位一组打印，空格分隔，肉眼就能对齐看掩码；调试时先打印预期掩码，再打印实际运算结果，差异一目了然。
2. 掩码注释
   在代码里写 // 0b1111_0000，让编译器帮你算常量；不要写 0xF0，因为十六进制仍需大脑转二进制。
3. 位运算单元测试
   把“置位、清除、切换、提取”四个基本操作写成测试，用数据驱动：输入整数、掩码、预期结果；一旦后续重构改错位，测试立即爆红。
4. 性能基准
   用 time 或 perf 对比“位运算版”与“原生版”CPU 周期；位运算优化必须给出量化收益，否则就是“为了炫技而炫技”。