位运算绝非什么奇技淫巧，它本质上是优秀程序员用单个整数来表达集合、状态或紧凑字段的智慧，核心目的是让 CPU 少干冤枉活。
我干开发这么多年，见过不少人把 XOR 交换变量当作秘技，把用位操作求绝对值当成绝学。他们可能花了几张草稿纸去推导，最终写出的代码虽然精简，却几乎没人能看懂。今天，我就把那些真正能在工程中提升生产力的位运算技巧梳理清楚，并告诉你哪些只是“面试幻觉”。
在开始之前，必须划一条红线：所有位运算操作，除非特别说明，必须作用于无符号整数（uint32_t / uint64_t）。因为有符号整数的右移、负数取反、溢出等在 C++ 标准中属于“未定义行为”或“实现定义行为”，跨平台时极易导致难以排查的 Bug。
一、集合与状态管理
1、判断奇偶：x & 1
别再写 x % 2 == 0 了。x & 1 不仅执行更快（一条 AND 指令），语义也更清晰——直接检查最低位。
if (x & 1u) {
// 奇数
}
应用场景：哈希分桶、线程 ID 路由、SIMD 通道分配。在程序的高频执行路径里，少一次取模运算，就少一次潜在的流水线停顿。
2、位标志操作：权限、开关、状态机
这是位运算最经典的应用场景。四个核心操作务必牢记：
using flags_t = uint32_t;
flags_t f{0};
f |= (1u << i); // 设置第 i 位
f &= ~(1u << i); // 清除第 i 位
f ^= (1u << i); // 翻转第 i 位
bool on = f & (1u << i); // 检查第 i 位
我曾在一个交易系统的订单生命周期管理中使用此技巧：bit0 表示已下单，bit1 表示部分成交，bit2 表示全成交，bit3 表示已撤单……状态转移就是几个简单的位操作，比使用 enum 配合 switch 语句快一个数量级，同时极大地节约了内存。
3、集合运算：并集、交集、差集
当用整数的每一位代表一个集合元素时，集合运算变得异常高效：
auto A_or_B = A | B; // 并集
auto A_and_B = A & B; // 交集
auto A_minus_B = A & ~B; // 差集 (A 有而 B 没有)
这在用户标签过滤、权限叠加、功能开关（Feature Gate）控制等场景下特别好用。一个 uint64_t 就能紧凑地存储 64 个布尔属性，对 CPU 缓存（Cache）极其友好。更多关于高效数据结构的设计思路，可以在云栈社区的算法与数据结构板块找到深入讨论。
二、位操作核心三件套
4、清除最低位的 1：x &= x - 1
这是遍历一个整数中所有置位（值为1）的位的黄金公式。
int popcount_naive(uint32_t x){
int c = 0;
while (x) {
x &= x - 1; // 每次循环清除最低位的1
++c;
}
return c; // c 即为 1 的个数
}
循环次数恰好等于该数中二进制 1 的个数。这个技巧广泛应用于树状数组（Fenwick Tree）、子集动态规划（DP）和布隆过滤器（Bloom Filter）的实现中。不过，在现代 C++ 中，最好不要自己实现统计 1 的个数，编译器有更优的指令。
5、获取最低位的 1（lowbit）：x & -x
必须使用无符号类型才能保证行为正确：
uint32_t lowbit(uint32_t x){
return x & -x;
}
其原理在于补码表示下 -x == (~x) + 1，因此 x & -x 的结果就是仅保留 x 中最低位的那个 1，其余位全为 0。树状数组（Binary Indexed Tree）的 update 和 query 操作就依赖这个操作来定位父节点。我在实现时间轮（Timing Wheel）定时器时，也用它来快速跳到最近的非空时间桶。
6、判断是否为 2 的幂
bool is_power_of_two(uint32_t x) {
return x != 0 && (x & (x - 1)) == 0;
}
应用场景：设计环形队列（掩码 mask = size - 1）、内存池的块大小对齐、快速傅里叶变换（FFT）长度的校验等。
三、枚举类高效技巧
7、枚举掩码的所有非空子集
这个技巧在算法/数据结构优化中，尤其是状态压缩动态规划里非常有用。
for (uint32_t sub = mask; sub; sub = (sub - 1) & mask) {
// sub 是 mask 的一个非空子集
}
此循环会跳过空集。如果需要包含空集，可以改用 do...while 循环：
uint32_t sub = mask;
do {
// 处理 sub
if (sub == 0) break;
sub = (sub - 1) & mask;
} while (true);
应用场景：状态压缩 DP、集合划分、权限组合的穷举测试。对于一个包含 k 个 1 的掩码，这个循环能精确地枚举出 2^k 个子集，效率远高于递归。
8、生成固定 k 个 1 的下一个组合
uint32_t next_combination(uint32_t x){
uint32_t u = x & -x; // lowbit
uint32_t v = u + x;
return v + (((v ^ x) / u) >> 2);
}
这个函数能按字典序生成所有恰好包含 k 个 1 的二进制掩码（假设输入 x 就是这样一个掩码）。我在做参数组合测试时，用它来遍历所有可能的开关配置，比深度优先搜索（DFS）快了近 5 倍。
四、位字段提取与内存对齐
9、提取指定位字段
// 从 x 中提取从 bit l 开始的 len 位
uint32_t extract_bits(uint32_t x, int l, int len){
return (x >> l) & ((1u << len) - 1);
}
例如，在 IPv4 头部，版本号（Version）占据高 4 位，可以这样获取：version = extract_bits(header, 28, 4)（假设 bit 0 是最低有效位）。自定义二进制协议常常将多个小整数打包进一个机器字（word）中，以节省网络带宽。
10、向上对齐到 2 的幂边界
// n 必须是 2 的幂
uint32_t align_up(uint32_t x, uint32_t n){
return (x + n - 1) & ~(n - 1);
}
内存分配器、DMA 缓冲区、页表对齐都依赖这个操作。重要前提：n 必须是 2 的幂，否则计算结果将是错误的。
11、乘除 2 的幂：用移位代替
x << 3; // 等价于 x * 8
x >> 2; // 等价于 x / 4，仅对非负无符号数成立
关键点：只能对 uint32_t/uint64_t 或明确为非负的值使用右移代替除法。有符号数的右移在不同平台上的行为（算术右移或逻辑右移）可能不一致，容易引发未定义行为。
五、位重排与校验
12、位反转（Bit Reversal）
uint32_t reverse_bits(uint32_t x) {
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
return (x << 16) | (x >> 16);
}
这个分治算法在 FFT 的位反转重排、Z-order 曲线计算以及某些哈希函数构造中会用到。理解它对深入掌握计算机基础中的位操作逻辑很有帮助。
六、拥抱现代C++标准库
不要再手写 popcount 之类的函数了！C++20 在 <bit> 头文件中提供了丰富的位操作函数，如 std::popcount、std::countr_zero、std::bit_ceil。编译器会将它们翻译成 POPCNT、LZCNT 等单条 CPU 指令，不仅比你手写的快，而且绝对安全、可移植。
#include <bit>
std::popcount(x); // 1 的个数
std::countr_zero(x); // 末尾 0 的个数
std::countl_zero(x); // 前导 0 的个数
std::rotl(x, n); // 循环左移
std::bit_ceil(x); // 向上取 2 的幂
什么时候值得使用位运算？ 一个简单的判断标准：你是否在用整数的二进制位来表达某种结构化的信息。
如果是用于表示集合、协议字段、紧凑的状态机，那么请大胆使用。但如果仅仅是为了省掉一条指令，或者炫技般地使用 XOR 交换变量，那还是算了吧。
举一个真实的性能案例：我们曾有一个风控引擎，最初使用 std::vector<bool> 存储 20 多条规则状态，每个请求需要随机访问这 20 多个位置，导致 L1 Cache 未命中率高达 18%。后来将其改为一个 uint32_t 位掩码，一次加载即可获得所有规则状态，Cache 未命中率骤降至 2%，系统 QPS 从 8 万跃升至 22 万。这并不是因为位运算本身有多神奇，而是我们通过它避免了让 CPU 进行大量低效的随机内存访问，跑了冤枉路。
现在，你还会在代码里用 % 2 来判断奇偶吗？你是否也曾用 std::vector 来管理大量的布尔状态，并与性能瓶颈苦苦搏斗过呢？
发表于 16 小时前
|
查看: 0|
回复: 0
