others

位运算技巧与陷阱

系统梳理位运算（bitwise operation）的底层表示与工程用法：二进制补码与符号扩展、与或异或取反移位的真值语义、掩码与位标志（bit flag）、lowbit/popcount/位反转等经典技巧、有符号右移与移位越界的未定义行为、跨语言（C/Java/Go/Python/JS）差异、位图与集合压缩、无分支优化的适用边界与可读性权衡。

Leeting Yan 2026-10-07 8 分钟阅读 3523 字

引言

位运算（bitwise operation）是少数「编译到硬件就是一条 ALU 指令」的运算：与（AND）、或（OR）、异或（XOR）、取反（NOT）、左移、右移，各自对应 CPU 里的一次操作。它既能让状态压缩、集合运算、协议解析快到极致，也是 bug 的温床——有符号右移的符号扩展、移位量超过字长的未定义行为、& 与 == 的优先级陷阱，任何一个都足以让代码在生产环境里静默出错。

本文从补码表示讲到实战技巧，再到跨语言差异与性能边界。目标很明确：让你在该用位运算的地方用得精确，在不该用的地方果断用可读性更高的写法替代。

前置：二进制与编码工具、浮点数与 IEEE 754 。算法练习可参考位运算题目集。

1. 补码表示：一切的起点

计算机里的整数几乎都用**二进制补码（two’s complement）**表示。理解它是理解位运算行为的前提。

1.1 补码的取值规则

对于 n 位有符号整数，最高位（MSB）是符号位，权重为 -2^(n-1)，其余位权重为正：

位宽	范围	0x80 的十进制	0xFF 的十进制
int8	-128 ~ 127	-128	-1
int16	-32768 ~ 32767	-32768	-1
int32	-2147483648 ~ 2147483647	-2147483648	-1
int64	-2^63 ~ 2^63-1	-2^63	-1

关键性质：

~x == -x - 1，即取反等价于「取负再减一」。
-x == (~x) + 1，这是「取负」的位运算实现。
补码让加减法共用一套电路：a - b == a + (~b) + 1，无需单独的减法器。

1.2 为什么不是原码或反码

原码（sign-magnitude）有 +0 和 -0 两个零，反码（one’s complement）也有两个零且需要循环进位。补码只有一个零，且溢出是「回绕」而非未定义，这正是现代 CPU 采用它的原因。代价是：你无法直接从位模式读出负数的绝对值，必须先理解符号扩展。

# Python 的整数是任意精度，没有固定字长，因此要手动模拟 8 位
def to_int8(x):
    x &= 0xFF
    return x - 256 if x >= 128 else x

print(to_int8(0xFF))   # -1
print(to_int8(0x80))   # -128
print(to_int8(0x7F))   # 127

2. 基础运算与真值语义

2.1 五种基本运算

运算	符号	规则	典型用途
与 AND	`&`	都为 1 才为 1	取位、清位、掩码
或 OR	`\|`	有一个 1 就为 1	置位、合并标志
异或 XOR	`^`	不同为 1	翻转、交换、校验
取反 NOT	`~`	逐位翻转	生成掩码
左移 SHL	`<<`	低位补 0	乘 2 的幂
右移 SHR	`>>`	视符号决定补位	除 2 的幂

2.2 运算符优先级陷阱

位运算符的优先级低于比较运算符，这是最常见的坑：

// 错误：先算 (flags & MASK) == MASK 会变成 flags & (MASK == MASK) == flags & 1
if (flags & MASK == MASK) { ... }

// 正确：加括号
if ((flags & MASK) == MASK) { ... }

优先级从高到低大致为：~ > 移位 > 关系运算 > & > ^ > |。记忆口诀：移位像算术，&/^/| 像逻辑。Java 里同样的陷阱存在，IDE 会告警但不会报错。

2.3 逻辑运算与位运算不可混用

&&、|| 是短路逻辑运算，返回布尔值；&、| 是逐位运算，返回整数。在 C 里 if (a & b) 和 if (a && b) 语义完全不同：

int a = 2, b = 4;
printf("%d\n", a & b);    // 0（按位与）
printf("%d\n", a && b);   // 1（逻辑与，非零即真）

3. 经典位技巧

3.1 lowbit：取出最低位的 1

x & (-x) 取出 x 最低位的 1 所代表的数值，是树状数组（Fenwick Tree）的核心。

def lowbit(x):
    return x & (-x)

print(lowbit(12))   # 12 = 0b1100 -> 0b0100 = 4
print(lowbit(10))   # 10 = 0b1010 -> 0b0010 = 2

3.2 清除最低位的 1

x & (x - 1) 把最低位的 1 清零，可用来统计 1 的个数或判断是否为 2 的幂：

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

def popcount_kernighan(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

print(popcount_kernighan(0b1011011))   # 5

3.3 硬件 popcount

现代 CPU 有 POPCNT 指令，编译器/语言通常直接暴露：

// GCC/Clang 内建
int n = __builtin_popcount(x);
// C++20
#include <bit>
int m = std::popcount(x);

// Java 的 Integer.bitCount 会编译成 POPCNT（若目标 CPU 支持）
int n = Integer.bitCount(x);

3.4 位反转与字节序翻转

def reverse_bits(x, width=32):
    r = 0
    for _ in range(width):
        r = (r << 1) | (x & 1)
        x >>= 1
    return r

对于字节序（endianness）翻转，用位运算比循环更快：

uint32_t bswap32(uint32_t x) {
    return ((x & 0xFF000000) >> 24) |
           ((x & 0x00FF0000) >> 8)  |
           ((x & 0x0000FF00) << 8)  |
           ((x & 0x000000FF) << 24);
}

3.5 无临时变量交换

a ^= b; b ^= a; a ^= b;   // 交换 a、b

这个技巧有前提：a 与 b 必须是不同内存地址。若 a 和 b 指向同一变量（如 swap(&arr[i], &arr[j]) 且 i == j），结果会把值清零。工程上几乎总该用临时变量——现代编译器生成的代码一样快，且无别名风险。

4. 掩码与位标志

4.1 位标志（bit flag）设计

用一个整数的每一位表示一个布尔状态，比多个 bool 字段更省内存，也更便于整体传递。

#define FLAG_READ     (1 << 0)   // 0x01
#define FLAG_WRITE    (1 << 1)   // 0x02
#define FLAG_EXEC     (1 << 2)   // 0x04
#define FLAG_HIDDEN   (1 << 3)   // 0x08

unsigned int perm = FLAG_READ | FLAG_WRITE;

int can_read  = (perm & FLAG_READ) != 0;
int can_exec  = (perm & FLAG_EXEC) != 0;
perm |= FLAG_EXEC;             // 置位
perm &= ~FLAG_WRITE;           // 清位
perm ^= FLAG_HIDDEN;           // 翻转

4.2 掩码的构造与提取

def get_field(value, shift, width):
    mask = (1 << width) - 1
    return (value >> shift) & mask

def set_field(value, shift, width, field):
    mask = (1 << width) - 1
    return (value & ~(mask << shift)) | ((field & mask) << shift)

v = 0
v = set_field(v, 4, 3, 0b101)   # 在 bit4..bit6 写入 5
print(bin(v))                    # 0b1010000
print(get_field(v, 4, 3))        # 5

这是协议解析（如 IPv4 头、TCP 标志、TLV 字段）的通用模式。注意 (1 << width) - 1 在 width 等于字长时会溢出，需特判。

4.3 集合运算的位表示

当全集规模较小（≤ 64）时，可用一个整数的位表示子集，交并补直接映射到位运算：

集合运算	位运算	含义
交集 A ∩ B	`A & B`	共同元素
并集 A ∪ B	`A \| B`	全部元素
差集 A \ B	`A & ~B`	在 A 不在 B
对称差	`A ^ B`	恰在一个集合中
判空	`A == 0`	空集
判断属于	`(A >> i) & 1`	元素 i 是否在内
添加元素	`A \| (1 << i)`	加入 i

5. 溢出、未定义行为与跨语言差异

这是位运算最容易踩雷的地方。位运算的语义在不同语言里差别极大。

5.1 移位越界

语言	移位量 ≥ 位宽的行为
C / C++	未定义行为（UB），结果不可预测
Java	取移位量对 32（long 对 64）取模
Go	若移位量为变量，结果为 0；常量则编译期报错
Rust	调试模式 panic，发布模式回绕（可用 `wrapping_shl`）
Python	无固定字长，左移相当于乘 2 的幂，不溢出
JavaScript	取模 32，且按 32 位有符号处理

// Java：移位量被 mod 32
System.out.println(1 << 32);   // 1，不是 0
System.out.println(1 << 33);   // 2

// Go：变量移位越界得 0
var s uint = 32
var x int32 = 1
fmt.Println(x << s)   // 0

5.2 有符号右移：算术移位 vs 逻辑移位

>> 对负数补的是符号位（算术移位），>>>（Java/JS）才是补 0 的逻辑移位：

int a = -8;                 // 0xFFFFFFF8
System.out.println(a >> 1);    // -4，保留符号
System.out.println(a >>> 1);   // 2147483644，高位补 0

C 语言里 >> 对负数是实现定义的（implementation-defined），几乎所有编译器做算术移位，但标准不保证。要可移植就用无符号类型。

5.3 左移溢出

有符号整数左移导致符号位变化，在 C 中是 UB：

int x = 1 << 31;   // UB！有符号溢出
unsigned u = 1u << 31;   // 合法，0x80000000

Java 里则明确定义为回绕，1 << 31 == Integer.MIN_VALUE。

5.4 语言能力速查

语言	整数模型	无符号类型	逻辑右移	任意精度
C/C++	固定字长	有	无（用无符号模拟）	需库
Java	固定 32/64	无（Java 8 起有 API）	`>>>`	BigInteger
Go	固定	有	无	math/big
Rust	固定	有	无	无内置
Python	任意精度	无（统一）	无	原生
JavaScript	双精度浮点 + 32 位位运算	无	`>>>`	BigInt

6. 位域、位图与工程应用

6.1 位域（bit field）

C 的位域把结构体字段精确打包到比特，常用于协议头：

struct ipv4_header {
    uint8_t  version_ihl;   // 实际是 version:4 + ihl:4
    // 更清晰的写法：
    // uint8_t version : 4;
    // uint8_t ihl     : 4;
    uint8_t  tos;
    uint16_t total_length;
};

位域的布局是实现定义的（位序、对齐、跨字节），跨平台二进制协议不要依赖它，改用手动掩码。

6.2 位图（bitmap）与布隆过滤器

用 uint64_t 数组表示海量布尔集合，内存是 bool[] 的 1/8：

class Bitmap:
    def __init__(self, n):
        self.bits = bytearray((n + 7) // 8)
    def set(self, i):
        self.bits[i >> 3] |= 1 << (i & 7)
    def get(self, i):
        return (self.bits[i >> 3] >> (i & 7)) & 1
    def clear(self, i):
        self.bits[i >> 3] &= ~(1 << (i & 7))

位图是 Roaring Bitmap、布隆过滤器（Bloom Filter）、倒排索引的基础。更多哈希相关结构见哈希表与一致性哈希。

6.3 颜色与像素操作

RGBA 打包进 32 位整数是位运算的经典场景：

def pack_rgba(r, g, b, a):
    return (r << 24) | (g << 16) | (b << 8) | a

def unpack_rgba(px):
    return (px >> 24) & 0xFF, (px >> 16) & 0xFF, (px >> 8) & 0xFF, px & 0xFF

7. 无分支优化与性能边界

7.1 什么时候位运算真的更快

分支预测失败代价约 10~20 个周期，位运算往往 1 个周期。因此把分支改写成算术/位运算（branchless）在热点循环里可能显著加速：

// 有分支
int abs_branch(int x) { return x < 0 ? -x : x; }

// 无分支（补码技巧）
int abs_branchless(int x) {
    int mask = x >> 31;          // 负数全 1，非负全 0
    return (x + mask) ^ mask;
}

7.2 现代编译器的自动优化

abs、min、max 这类模式，编译器通常已能生成 CMOV（条件传送）或 SETcc 指令，手写无分支反而可能更慢或更晦涩。先 profile，再优化。用 objdump -d 或 gcc -S 确认生成的汇编。

7.3 可读性权衡清单

场景	建议
协议/格式解析、位标志	用位运算，天然合适
集合运算（小全集）	用位表示，简洁高效
热点循环的除法取模	若除数是 2 的幂，用移位
普通业务逻辑	优先可读性，别炫技
手写 swap / abs / min	交给编译器或标准库
跨语言共享的位操作	显式用无符号 + 固定宽度类型

7.4 除 2 的幂的正确写法

// 有符号负数右移不等于整除（向下取整 vs 向零取整）
int a = -7;
printf("%d\n", a / 2);    // -3（向零取整）
printf("%d\n", a >> 1);   // -4（向下取整）

这是把 >> 当除法用时的经典错误。要等价于 / 2^k，负数需补偿：(a + (1 << k) - 1) >> k（对 a < 0）。

8. 小结

位运算的价值在于「精确表达硬件语义」：当你在处理协议、标志位、集合、像素或性能热点时，它是不可替代的工具；而在普通业务逻辑里，它更多是可读性的负担。记住三条底线：移位量别越界、有符号右移别当除法、跨语言时显式固定宽度和无符号性。掌握补码、掩码与 lowbit 这几块基石，绝大多数位运算技巧都能自己推导出来。需要进一步对照字节层细节，可回到二进制与编码工具与浮点数与 IEEE 754 。

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章返回首页

引言