位运算技巧
2026-04-04 18:22:25

常见位运算技巧

技巧表达式 作用 示例
n & (n - 1) 将最低位的 1 变成 0（清除最低位的 1） 12 (1100) -> 8 (1000)
n & -n 提取最低位的 1（得到 2^k 形式的数） 12 (1100) -> 4 (0100)
n | (n + 1) 将最低位的 0 变成 1 9 (1001) -> 11 (1011)
n | (n - 1) 将末尾连续 0 变成 1 8 (1000) -> 15 (1111)
n & (n + 1) 将末尾连续 1 变成 0 7 (0111) -> 0
(n & (n - 1)) == 0 判断 n 是否为 2 的幂（或 0） 8 -> true, 6 -> false
x ^ y 按位异或，可用于无临时变量交换、寻找只出现一次的数 -
(x ^ y) >= 0 判断 x 和 y 是否同号（最高位相同） -
n >> 31 获取符号位（对于 32 位 int，负数得 -1，非负数得 0） -
(n ^ (n >> 31)) - (n >> 31) 求绝对值（兼容正负） -
while (n) { cnt++; n &= n-1; } 计算二进制中 1 的个数（popcount） -
sub = (sub - 1) & super 枚举超级集合 super 的所有子集 -

举例说明

1. 清除最低位的 1
n = 0b10110 (22)
n-1 = 0b10101
n & (n-1) = 0b10100 (20) ✅

2. 提取最低位的 1
n = 0b10110 (22)
-n = 0b01010 (补码)
n & -n = 0b00010 (2) ✅

3. 将最低位的 0 变成 1
n = 0b10101 (21)
n+1 = 0b10110
n | (n+1) = 0b10111 (23) ✅

4. 将末尾连续 0 变成 1
n = 0b10000 (16)
n-1 = 0b01111
n | (n-1) = 0b11111 (31) ✅

5. 判断 2 的幂
n = 16 → n & (n-1) = 0 ✅
n = 18 → n & (n-1) = 16 ≠ 0 ❌

HashMap 核心技巧

  • 底层：数组 + 链表/红黑树（链表长度 ≥8 且数组 ≥64 时树化；红黑树节点 ≤6 时退化为链表）
  • 哈希扰动：(h = key.hashCode()) ^ (h >>> 16) → 混合高位低位，减少碰撞
  • 取模优化：(n - 1) & hash 代替 hash % n（要求 n 为 2 的幂）
  • 扩容时机：size > threshold = capacity * loadFactor（默认 0.75）
  • 扩容机制：新容量翻倍（oldCap << 1），元素重新分配 → 索引要么不变，要么 oldIndex + oldCap
  • 树化阈值：链表长度 ≥8 且数组 ≥64 → 转为红黑树，提升极端碰撞下的查询效率

ConcurrentHashMap 核心技巧

  • 锁粒度：JDK 8+ 采用 CAS + synchronized 锁桶（Node 的头节点），放弃分段锁，降低锁竞争
  • 初始化：使用 sizeCtl 控制多线程并发初始化（CAS 保证单次）
  • put 流程：
    • 桶为空 → CAS 插入头节点
    • 桶非空 → synchronized 锁住头节点，进行链表/红黑树插入
  • 扩容：支持多线程协助扩容（每个线程负责一部分桶迁移），通过 transferIndex 分配任务，sizeCtl 标记状态
  • 计数：LongAdder 思想 → baseCount + CounterCell[] 分散计数，减少竞争
  • 弱一致性：迭代器（如 entrySet().iterator()）不抛出 ConcurrentModificationException，允许遍历过程中修改

通用技巧

  • 初始化容量：预估 expectedSize / loadFactor + 1 避免频繁扩容
  • key 不可变：保证 hash 值稳定（尤其是放入后修改会导致丢失）
  • ConcurrentHashMap 不允许 null key/value（HashMap 允许一个 null key）
上一页
2026-04-04 18:22:25