位运算技巧

#算法 · #位运算 · #状态压缩 · #异或 · #掩码

位运算是最接近硬件的操作，在系统编程、算法优化、状态压缩等场景中无处不在。掌握位运算的核心模式，能让你写出更高效、更优雅的代码。

1. 基础操作

1.1 六个基本位运算

运算符	名称	效果	示例 (a=5=0b101, b=3=0b011)
`&`	按位与	两位都为 1 则为 1	`a & b = 0b001 = 1`
`\|`	按位或	至少一位为 1 则为 1	`a \| b = 0b111 = 7`
`^`	异或	两位不同则为 1	`a ^ b = 0b110 = 6`
`~`	按位取反	0 变 1，1 变 0	`~a = -6`（补码）
`<<`	左移	各二进制位左移，低位补 0	`a << 1 = 0b1010 = 10`
`>>`	右移	各二进制位右移，高位补符号位	`a >> 1 = 0b10 = 2`

1.2 常用恒等式

x ^ 0 = x         异或 0 不变
x ^ x = 0         异或自身得 0
x ^ y = y ^ x     交换律
(x ^ y) ^ z = x ^ (y ^ z)  结合律

x & (x - 1)       → 将最低位的 1 清零
x & -x            → 只保留最低位的 1（lowbit）
x | (x + 1)       → 将最低位的 0 置为 1
x | (x - 1)       → 将最低位 1 右边的 0 全变 1

1.3 补码原理深解

为什么 ~a = -6（当 a=5 时）？ 理解这一点需要理解计算机如何表示负数。

补码（Two's Complement）的数学定义

在 n 位系统中，一个数 x 的补码定义为：

补码(x) = x (x ≥ 0)
补码(x) = 2ⁿ - |x| (x < 0)

等价公式：负数的补码 = 按位取反 + 1，即 -x = ~x + 1。

为什么用补码？—— 统一加减法

问题: 用原码（sign-magnitude）做 5 + (-3)

原码:  5 = 0b0101
       -3 = 0b1011 (最高位是符号位)
直接加: 0b0101 + 0b1011 = 0b10000 = 16？？ 完全错误 ❌

补码:  5  = 0b0101
       -3 = 0b1101 (按位取反 0b0011 + 1 = 0b1101)
直接加: 0b0101 + 0b1101 = 0b10010 → 溢出忽略了最高位 = 0b0010 = 2 ✅

结论: 补码让加法器同时处理加法和减法，不需要额外的减法电路。

补码的对称性

n=4 位补码的范围: [-8, 7]
  正数: 0 到 7 = 0b0000 到 0b0111
  负数: -1 到 -8 = 0b1111 到 0b1000

关键不对称性: 负数比正数多一个 → math.MinInt 没有对应的正数
  8 位:  [-128, 127]   → MinInt8 = -128, MaxInt8 = 127
  64位:  [-2⁶³, 2⁶³-1] → MinInt64 = -2⁶³, 而 2⁶³ 无法用 int64 表示

这是 Go 中 -MinInt 溢出的根源：

x := math.MinInt64  // -9223372036854775808
-x                   // 溢出！2⁶³ 无法用 int64 表示，结果 = MinInt64 自身

有符号右移 vs 无符号右移

// Go 中的 >> 是算术右移（保留符号位）
var a int8 = -8   // 0b11111000
a >> 1            // 0b11111100 = -4  ← 高位补 1（保持负数）

// 无符号数的 >> 是逻辑右移（高位补 0）
var b uint8 = 248 // 0b11111000
b >> 1            // 0b01111100 = 124  ← 高位补 0

关键区别：有符号 >> 补符号位，无符号 >> 补 0。Go 不像 Java 有 >>> 运算符，无符号右移只需用 uint 类型。

为什么 `x & -x` 能取最低位 1？

x = 20  = 0b00010100
-x = -20 = 按位取反+1
~x       = 0b11101011
~x + 1   = 0b11101100

x & -x:   0b00010100
         & 0b11101100
         = 0b00000100 → 只保留了最低位的 1 ✅

原理: 取反后，最低位 1 及右边的 0 变成完全相同的形式，相与后保留。

Go 中位运算的坑

// 坑1: int 在 32/64 位系统上大小不同
// 以下代码在 32 位机器上行为不同：
var x int = 1
x << 33  // 32位系统编译错误！64位系统正常

// 坑2: 移位操作符的右操作数必须是无符号整数
var i uint = 3
x << i  // ✅
// x << 3  // ✅ 常量也 OK

// 坑3: ^ 在不同类型上含义不同
var a int = 5
^a       // 按位取反 = -6
var b uint = 5
^b       // 按位取反 = 0xFFFFFFFFFFFFFFFA（取决于平台位数）

// 坑4: &^ 是 Go 特有的 "按位清除" 操作符
// a &^ b = a AND (NOT b)
a := 0b1111
b := 0b0101
a &^ b  // 0b1010 — 将 b 中为 1 的位在 a 中清零

2. 经典技巧

2.1 Brian Kernighan 算法：数 1 的个数

// 每次消除最低位的 1
func popcount(x int) int {
    count := 0
    for x != 0 {
        x &= x - 1    // 消除最低位的 1
        count++
    }
    return count
}

// Go 标准库: bits.OnesCount(uint(x))

时间复杂度：O（1 的个数），而非 O（位数）。对于稀疏位图极快。

2.2 lowbit：保留最低位 1

func lowbit(x int) int {
    return x & -x
    // 示例：x=12 (1100), lowbit=4 (0100)
}

关键应用：树状数组（Fenwick Tree）的核心操作。

2.3 判断 2 的幂

func isPowerOfTwo(x int) bool {
    return x > 0 && x&(x-1) == 0
}

2.4 交换两数（无临时变量）

a ^= b
b ^= a   // b = (a^b)^b = a
a ^= b   // a = (a^b)^a = b

2.5 只出现一次的数字

// 数组中除了一个数出现一次，其余都出现两次。找出它。
func singleNumber(nums []int) int {
    result := 0
    for _, n := range nums {
        result ^= n    // a ^ a = 0, a ^ 0 = a
    }
    return result
}

推广：如果除了一个数出现一次，其余出现三次？→ 统计每个 bit 上 1 的个数，模 3。

2.6 大小写转换

// 大写 → 小写
ch := 'A' | ' '   // 'a'
// 小写 → 大写
ch := 'a' & '_'   // 'A'
// 大小写切换
ch := 'a' ^ ' '   // 'A'
ch := 'A' ^ ' '   // 'a'

原理：' '（空格）= 32 = 0b100000，ASCII 码中大小写字母恰好差 32。

2.7 取绝对值（无分支）

// 仅适用于 int32（Go 中需要处理符号位）
func abs(x int) int {
    // 算术右移：正数得 0，负数得 -1
    mask := x >> 63          // 在 64 位系统上
    return (x ^ mask) - mask
}

2.8 奇偶判断

x & 1 == 0  // 偶数
x & 1 == 1  // 奇数

3. 位掩码与状态压缩

3.1 集合表示

一个 int 的每个 bit 代表一个元素是否存在。可以表示 64 个元素。

set := 0
set |= 1 << k      // 加入元素 k
set &^= 1 << k     // 删除元素 k
set ^= 1 << k      // 切换元素 k
hasK := set>>k&1   // 检查元素 k 是否存在

// 遍历子集
for sub := set; sub > 0; sub = (sub - 1) & set {
    // sub 是 set 的一个子集
}

3.2 状态压缩 DP

经典应用：旅行商问题（TSP）、N 皇后、铺砖问题。

// TSP: dp[mask][i] = mask 表示的已访问城市集合，i 为当前位置
// dp[mask|(1<<j)][j] = min(dp[mask|(1<<j)][j], dp[mask][i] + dist[i][j])

3.3 位图（Bitmap）

用 bit 数组做去重/存在性判定，空间是布隆过滤器的基准线。

type Bitmap struct {
    bits []uint64
}

func (b *Bitmap) Set(pos int) {
    b.bits[pos/64] |= 1 << (pos % 64)
}

func (b *Bitmap) Test(pos int) bool {
    return b.bits[pos/64]>>(pos%64)&1 == 1
}

4. 快速幂

// 快速幂（二分幂）：O(log n)
func pow(x, n int64) int64 {
    result := int64(1)
    for n > 0 {
        if n&1 == 1 {   // n 的当前最低位为 1
            result *= x
        }
        x *= x
        n >>= 1
    }
    return result
}

// 带模运算的快速幂
func powMod(x, n, mod int64) int64 {
    result := int64(1)
    x %= mod
    for n > 0 {
        if n&1 == 1 {
            result = result * x % mod
        }
        x = x * x % mod
        n >>= 1
    }
    return result
}

5. 进位与溢出处理

5.1 加法（不用 + 号）

func add(a, b int) int {
    for b != 0 {
        carry := (a & b) << 1   // 进位
        a = a ^ b                // 无进位和
        b = carry
    }
    return a
}

5.2 两数之和（判断溢出）

// Go 1.18+ 有 built-in 溢出检查
import "math"

func safeAdd(a, b int) (int, bool) {
    if a > 0 && b > math.MaxInt-a {
        return 0, false  // 溢出
    }
    if a < 0 && b < math.MinInt-a {
        return 0, false  // 溢出
    }
    return a + b, true
}

6. 实战速查

需求	写法	说明
乘 2	`x << 1`	左移 1 位
除 2	`x >> 1`	算术右移（向下取整）
取模 2ⁿ	`x & ((1<<n) - 1)`	比 `x % 2ⁿ` 快
取反	`^x`	bitwise NOT
正数变负数	`~x + 1`	补码
平均值	`(x&y) + ((x^y)>>1)`	无溢出
最高位 1 的位置	`bits.Len(uint(x)) - 1`	Go 标准库
前导零	`bits.LeadingZeros(uint(x))`	Go 标准库

7. 工程场景

场景	位运算应用
Redis Bitmap	`SETBIT`/`GETBIT`/`BITCOUNT`，用户签到、日活统计
权限系统	`rbac
TCP Flags	SYN=2, ACK=16，`flags & SYN != 0`
IP 子网掩码	`192.168.1.0/24` 中的 `/24` = 前 24 位置 1
布隆过滤器	多个哈希函数映射到 bit 数组
UUID 生成	Snowflake 算法：timestamp 占 41 bit，机器 ID 10 bit，序列号 12 bit

7.1 SIMD 与位运算：并行加速的秘密


> **SIMD（Single Instruction, Multiple Data）** 是一条指令同时处理多个数据的 CPU 特性。位运算是 SIMD 最天然的加速场景——因为位运算天然无依赖、天然可并行。理解 SIMD 能让你明白为什么 modern CPU 上 `bits.OnesCount` 可以一条指令完成。

#### SIMD 思想

普通操作（SISD）：一次处理一个数据 CPU: A[i] + B[i] = C[i] → 循环 8 次

SIMD（128 bit 寄存器）：一次处理 4 个 int32 CPU: [A0,A1,A2,A3] + [B0,B1,B2,B3] = [C0,C1,C2,C3] → 循环 2 次使用 256-bit AVX2：一次处理 8 个 int32 使用 512-bit AVX-512：一次处理 16 个 int32


#### 关键 SIMD 指令集与位运算

| 指令集 | 寄存器宽度 | 支持的位运算 | Go 中如何利用 |
|--------|-----------|-------------|--------------|
| **SSE2** | 128 bit | AND/OR/XOR/移位 | `math/bits` 内部使用 |
| **AVX2** | 256 bit | 全部位运算 + 变量移位 | 编译器自动向量化 |
| **AVX-512** | 512 bit | 全部 + masked operations | 编译器自动向量化 / 手动 asm |
| **POPCNT** | — | 硬件 popcount | `bits.OnesCount` → 一条 CPU 指令 |
| **LZCNT** | — | 硬件前导零计数 | `bits.LeadingZeros` → 一条 CPU 指令 |

#### `bits.OnesCount` 的底层——POPCNT 指令

```go
// Go 代码:
count := bits.OnesCount(uint(x))

// 实际编译为一条 CPU 指令:
// POPCNT rax, rdi    ← 在支持 POPCNT 的 CPU 上，这是一条指令！

性能对比（64 位整数 popcount）：

方法	耗时	说明
循环逐位检查	~32 ns/op	O(位数)，慢
Brian Kernighan 算法	~8 ns/op	O(1 的个数)，取决于数据
查表法（256 项）	~2 ns/op	空间换时间
POPCNT 指令	~0.3 ns/op	硬件直接算，最快

Go 编译器自动向量化示例

// 这种循环会被 Go 编译器用 SIMD 自动优化（Go 1.18+）
func andArrays(a, b []int32) []int32 {
    result := make([]int32, len(a))
    for i := range a {
        result[i] = a[i] & b[i]   // 编译器可能用 VPAND（AVX）一次处理 8 个
    }
    return result
}

// 手动 SIMD（需汇编）的加速比在 3-8x
// 但现代编译器的自动向量化已经足够好，通常不需要手写

实际工程中的 SIMD 应用

场景	SIMD 加速	典型加速比
Redis Bitmap 的 BITCOUNT	POPCNT 指令	5-10x
JSON 解析器	SIMD 快速跳过量词（simdjson）	10-25x
字符串匹配	SSE4.2 PCMPESTRI 指令	3-7x
Base64 编解码	AVX2 并行查表	4-8x
布隆过滤器批量查询	AVX2 并行 hash	3-6x
图像处理（Alpha Blending）	AVX-512	8-12x

要点：math/bits 包的几乎所有函数（OnesCount、LeadingZeros、TrailingZeros、Len等）在支持的硬件上都编译为单条 CPU 指令。不需要你自己实现 SIMD，编译器已经替你做了。

参考

Bit Twiddling Hacks (Sean Eron Anderson)
Hacker's Delight (Henry S. Warren)
Go math/bits 包文档

位运算技巧 ​

1. 基础操作 ​

1.1 六个基本位运算 ​

1.2 常用恒等式 ​

1.3 补码原理深解 ​

补码（Two's Complement）的数学定义 ​

为什么用补码？—— 统一加减法 ​

补码的对称性 ​

有符号右移 vs 无符号右移 ​

为什么 x & -x 能取最低位 1？ ​

Go 中位运算的坑 ​

2. 经典技巧 ​

2.1 Brian Kernighan 算法：数 1 的个数 ​

2.2 lowbit：保留最低位 1 ​

2.3 判断 2 的幂 ​

2.4 交换两数（无临时变量） ​

2.5 只出现一次的数字 ​

2.6 大小写转换 ​

2.7 取绝对值（无分支） ​

2.8 奇偶判断 ​

3. 位掩码与状态压缩 ​

3.1 集合表示 ​

3.2 状态压缩 DP ​

3.3 位图（Bitmap） ​

4. 快速幂 ​

5. 进位与溢出处理 ​

5.1 加法（不用 + 号） ​

5.2 两数之和（判断溢出） ​

6. 实战速查 ​

7. 工程场景 ​

7.1 SIMD 与位运算：并行加速的秘密 ​

Go 编译器自动向量化示例 ​

实际工程中的 SIMD 应用 ​

参考 ​

💬 文章评论