算法必修课：位运算技巧完全指南

在算法竞赛与高并发系统中，位运算是效率的魔法钥匙。本文用通俗易懂的语言带你拆解所有高频技巧，让你从“比特”秒变“毫秒”。

二进制：计算机底层语言

二进制如何表达整数

计算机使用二进制 (base-2) 来存储整数：只有 0 和 1。

• 如果某一位为 1，称之为 置位 (set)。
• 如果某一位为 0，称之为 清零 (clear)。

例如：

1101₂
= 1·2³ + 1·2² + 0·2¹ + 1·2⁰
= 8 + 4 + 0 + 1 = 13

正整数直接用二进制展开存放；负整数通常用 补码 表示，保证加法和减法都能用同一套电路完成。

位运算符：一步到位的算力加速器

所有运算符在现代 CPU 中几乎都只需 一个时钟周期，与加法同速。

按位运算符

快速示例

n   = 0101 1000
m   = 0011 0111
--------------------
n & m = 0001 0000
n | m = 0111 1111
n ^ m = 0110 1111
~n    = 1010 0111

位移运算符

• >> k：右移 k 位，等价于整数除以 2ᵏ
• << k：左移 k 位，等价于乘以 2ᵏ（小心溢出）

小贴士：在大数据处理场景👉 一次位移可能顶得上一万次乘法

int x = 5;
int half = x >> 1;               // half = 2 (5/2)
int eightfold = x << 3;          // eightfold = 40 (5*8)

实用位运算技巧全览

1. 置位、清零与翻转

int n = 0b1010;

n |= (1 << 2);   // 将第2位(从0开始)置为1 -> 1110
n &= ~(1 << 3);  // 将第3位清零     -> 0110
n ^= (1 << 1);   // 将第1位翻转     -> 0100

2. 判断单个位是否为1

bool is_set(int num, int pos) {
    return num >> pos & 1;
}

3. 判断是否为 2 的幂次

bool is_power_of_two(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

4. 计算连续 1 的最低位

int lowbit (int x) {
    return x & -x;      // 可直接取得最低位的1
}

5. 统计二进制中 1 的个数（popcount）

• 内置函数：__builtin_popcount(x) (GCC/Clang)
• 若限制多重循环，可使用 Brian Kernighan 算法。

int popcount(int x) {
    int cnt = 0;
    while (x) {
        x &= x - 1;
        cnt++;
    }
    return cnt;
}

经典竞赛场景示例

子集枚举

给定元素集合 S = {a, b, c}，用 int mask 表示子集：
若 mask & (1 << i) 置位，说明元素 i 被选中。

for (int mask = 0; mask < (1 << n); ++mask) {
    // 枚举 2^n 个子集
}

状态压缩 DP

在 15 位棋盘问题或旅行商问题中，用 32 位整数的每一位表示棋盘/城市是否走过，可将状态压缩至极致，显著提升效率。

👉 看看如何用 CPU 一次运算搞定百万种状态

FAQ：高频疑问一次讲透

Q1： 位运算会不会提升过头导致代码可读性变差？
A： 当逻辑超过 3 层嵌套时，建议用清晰注释或宏封装，保持 可维护性 与高性能兼顾。

Q2： >> 对负数安全吗？
A： C++20 前，右移负值的行为依赖实现；若需跨平台，将整型转成无符号再做位移。

Q3： 如何用位运算加速内存对齐？
A： 将地址对齐到 2ᵏ 的倍数可直接用 (addr + (k - 1)) & ~(k - 1)。

Q4： 哈希时能直接用异或吗？
A： 异或运算速度快，但要注意避免冲突。推荐再乘以一个大质数并累加。

Q5： Linux 如何用文件权限位控制读写？
A： 文件权限 rwxrwxrwx 就是 9 bit，用 0777 & ~umask 等位运算可一行计算最终权限。

结语：把运算成本降到最低

掌握位运算，就像在写五线谱上的休止符——看似微小，却能显著提升整段旋律的律动。无论是 算法竞赛 还是 交易撮合引擎，善用 bit manipulation 都能让你把 CPU 时钟周期榨到极致。下一步，赶快把文中代码搬到 IDE，感受毫秒级速度跃升吧！