为什么按位与运算要比取模运算高效？

#计算机网络#操作系统#面试八股

为什么按位与运算要比取模运算高效？

因为除法是 CPU 里最慢的整数指令之一，而按位与是一个周期的逻辑操作。当除数是 2 的幂时， x % 2^n 与 x & (2^n - 1) 数学上等价，编译器会自动做这个替换；手写位运算的意义在于 让运行时才知道的除数也能走这条快路径——哈希表容量取 2 的幂就是这个原因。

1. 差多少

操作典型延迟（现代 x86）说明
and1 周期单周期、可流水
add/sub/shl1 周期同上
imul3~5 周期流水化较好
idiv/div20~40+ 周期微码实现，阻塞流水线

取模更糟的是它不只慢，还不可预测：除数变化时延迟不稳定，乱序执行难以掩盖； 而 and 是固定 1 周期，CPU 可以放心地并行发射多条。

x % 8 的汇编（除数已知为 2 的幂，编译器优化后）：
    and  eax, 7          ; 一条指令

x % n 的汇编（n 是运行时变量）：
    cdq                  ; 符号扩展
    idiv ecx             ; 20~40 周期，且阻塞后续依赖

2. 数学上为什么成立

设 n = 2^k，则 x = q × 2^k + r，其中 0 ≤ r < 2^k
2^k 的二进制是 1 后面 k 个 0，减 1 后变成 k 个 1 的掩码
x & (2^k - 1) 恰好取出 x 的低 k 位，即余数 r
例：x = 29 = 0b11101，k = 3
    29 % 8 = 5
    29 & 7 = 0b11101 & 0b00111 = 0b00101 = 5   ✓

注意前提：x 必须是非负整数。对负数，C/Go/Java 的 % 取余符号跟被除数走（-7 % 4 == -3）， 而 -7 & 3 == 1，两者不等价。所以哈希表里通常先做一次无符号转换或保证 hash 非负。

3. 代码里怎么用

// JDK HashMap：容量强制为 2 的幂，定位桶时用 & 代替 %
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  // 扰动，让高位参与
}
// n 是容量，必为 2 的幂
int index = (n - 1) & hash;      // 等价于 hash % n，但只需 1 个周期

// Go map 的桶数也是 2 的幂（B 决定 2^B 个桶）
// 取桶下标：hash & bucketMask，bucketMask = 1<<B - 1

// 自己写环形缓冲区时同样适用
type Ring struct {
    buf  []byte
    mask int   // len(buf)-1，len 必须是 2 的幂
    head int
    tail int
}

func (r *Ring) idx(i int) int { return i & r.mask }   // 比 i % len(r.buf) 快

// 编译器能识别常量除法的强度削减（strength reduction）
size_t a = x % 16;     // 编译后就是 and
size_t b = x % n;      // n 是变量，只能真除法

// 想对变量也走位运算，就自己保证 n 是 2 的幂
if ((n & (n - 1)) == 0) {   // 判断 n 是否为 2 的幂
    r = x & (n - 1);
}

4. 常见追问

Q：那为什么很多哈希表不干脆用质数取模？ 质数能让哈希值分布更均匀，抵御特定模式的冲突（比如 key 都是偶数）。而 2 的幂取模只取低位， 低位规律性强时冲突严重，所以 HashMap 额外做了"高 16 位异或低 16 位"的扰动来打散。 Java 选择了"2 的幂 + 扰动 + 扩容 rehash"，是速度与分布的折中。

Q：现代 CPU 的除法还这么慢吗？ 是的。整数除法用迭代式微码实现，延迟随操作数位宽增长，通常 20~40 周期且不完全流水化。 浮点除法相对好些但仍在 10 周期以上。所以"避免除法"至今仍是有效的优化。

Q：编译器不是会自动优化吗？ 对常量除数会，这叫强度削减；对运行时变量不会，因为编译器不知道它是不是 2 的幂。 所以热点路径上要么把容量约束成 2 的幂，要么用乘魔数（reciprocal multiplication）手工替换。

Q：位运算有什么坑？ 一是符号：负数右移、取模语义不同语言有差异；二是溢出：1 << 31 在 32 位有符号里是负数； 三是可读性：(x & 7) 不如 x % 8 直观，加注释或封装成函数更稳妥。

小结

% 慢在除法指令（20~40 周期且不可流水），& 只要 1 个周期。除数为 2 的幂时二者数学等价， 前提是非负整数。工程上的标准做法是"容量取 2 的幂 + 掩码定位 + 高位扰动"， HashMap、Go map、环形缓冲区都是这个套路。

笔记加载中…