什么是位运算算法？
位运算算法是直接在二进制位（bit）上操作的计算技术，也被称为位运算优化。这些算法通过对 0 和 1 组成的二进制数字进行与、或、异或、取反及移位等原子级操作，把算术或逻辑任务转成极轻量的指令，进而获得更高的速度与更低的内存占用。
换句话说，当我们用位运算对数据进行筛选、压缩、加密或掩码处理时，CPU 只需在底层寄存器里一次性解决，而无需逐位循环，减少了分支判断，降低 cache miss，大幅提升性能。
👉 想一次性掌握 30+ 高频位运算技巧？点我立刻解锁完整指南！
位运算基础：六大运算符快速记忆
| 运算符 | ANSI 名称 | 功能概要 | |
|---|---|---|---|
& | 与(AND) | 同位均为 1 才得 1 | |
| `\ | ` | 或(OR) | 任一位为 1 即得 1 |
^ | 异或(XOR) | 不同得 1，相同得 0 | |
~ | 取反(NOT) | 0 变 1，1 变 0 | |
<< | 左移(SHL) | 整体左移，低位补 0，等同 ×2^n | |
>> | 右移(SHR) | 整体右移，高位补 符号位/0，等同 ÷2^n |
1. 与 (&) 运算
- 真值表
1 & 1 = 1，其余三种组合均为 0 - 场景示例
清零特定比特：x & ~(1 << n)，常用来快速关闭位标志。
2. 或 (|) 运算
- 真值表
0 | 0 = 0，其余三种组合均为 1 - 场景示例
置位特定比特：x | (1 << n)，批量打开权限时尤其方便。
3. 异或 (^) 运算
- 真值表
只有输入不一致时才得 1 场景示例
交换两数不借助临时变量：a ^= b; b ^= a; // b = original a a ^= b; // a = original b常用于强频率内存压缩。
4. 取反 (~) 运算
- 对所有位取补码，机器级还原超快。
- 场景：快速计算
-x的补码，~x + 1。
5. 左移 (<<) 运算
- 把比特位整体左移后自动补 0。
例如：5 << 3⟶101000（二进制） ⟶ 40（十进制）
6. 右移 (>>) 运算
- 无符号：高位补 0；有符号：高位补符号位。
例子：-8 >> 1在四字节两补码中会得到-4，而8 >> 1得 4。
实战应用：位运算无处不在
- 哈希优化：用
x & (size-1)代替模运算完成哈希散列，节省大量乘法指令。 - 权限系统：每个功能用一个单独的 bit 管理，组合为
uint32_t bitmask，直接一次位运算即可解析用户权限。 - 网络校验：利用 XOR 做奇偶校验，高效检测 TCP 报文篡改。
- 图像处理：对像素 alpha 通道做混合运算时，位运算比浮点乘法快 3–5 倍。
- 加密货币：挖矿算法内部大量使用 SHA-variant 位运算，显著节省能量。
高频练习：一步到位的 10 大比特题
- 置位第 n 位：
num |= (1 << n) - 清除第 n 位：
num &= ~(1 << n) - 检测第 n 位是否为 1：
if(num & (1 << n)) - 取反第 n 位：
num ^= (1 << n) 计算二进制中 1 的个数：算法 Brian Kernighan 速记版
int count = 0; while(n) { n &= n-1; count++; }- 判断是否为 2 的幂：
return (n > 0) && !(n & (n-1)); - 找到最右侧 1 的位置：
n & -n(利用两补码特性) - 按位旋转整数（循环左移/右移）
- 用位运算实现
abs()：<(x ^ (x >> 31)) - (x >> 31)> - 生成格雷码：
mask = i ^ (i >> 1)，广泛用于工业 ADC。
QA 抓重点：你可能忽视的 5 个细节
Q1: 位运算一定比加减乘除快吗？
A1: 在大多数主流处理器上，位运算比等价算术操作快 2–10 倍；但对常量乘除 2 的幂，x * 8 会被编译器自动优化为 x << 3，两者速度几乎无差异。
Q2: 浮点数能用位运算吗？
A2: 直接对 float/double 做位操作属于未定义行为 (UB)；通常先 memcpy 到整数寄存器，再操作，或直接使用 std::bit_cast（C++20）。
Q3: 中小端字节序会影响位运算结果吗？
A3: 不会。位运算是逻辑层面操作，发生在 CPU 寄存器内，不受字节序影响。注意的是左右移针对数值而非字节序。
Q4: 位运算会带来可读性灾难吗？
A4: 过度内联位运算确实降低可维护性。建议：
- 统一封装宏/函数
set_bit(idx)、is_pow2(x)等； - 写充分注释；
- 在 team review 时提供测试用例。
Q5: 能在 Python/Java 中一样高效地使用位运算吗？
A5: 语言虚拟机通常已做 JIT 优化，位运算依旧比算术更快；但 Python 的 int 是可变长度大整数，内存模型与 C 不同，频繁大整数位运算效率略低，建议使用 bitarray 或 numpy 向量化。
写在最后
掌握位运算算法不仅能让你写出超高性能的底层代码，在加密工程、游戏引擎、实时系统、区块链等场景中更是必不可少的核心竞争力。
本文覆盖了位运算概念、核心运算符以及高频实战技巧，配合详细的代码片段与典型题库，助你在算法面试和实战项目中所向披靡。立即手撕 Bitmask，开启微观级性能优化之旅！