← 目录 / C++ 编程语法
位运算直接操作二进制位，速度极快（比乘除法快得多），是竞赛编程的核心技巧。所有位运算都针对补码进行。
7.1
之前所有的运算符（+ - * / % 等）都是把数字当成一个整体来计算，而位运算则完全不同——它直接拆开数字底层的二进制表示（见 2.3 节原码反码补码），一位一位地进行操作。
这样做有什么好处？两个原因：一是速度极快，位运算是 CPU 最底层支持的操作，比乘除法快得多；二是能实现一些用普通算术运算很难甚至无法做到的技巧，比如用一个整数同时表示"32 个开关的状态"（状态压缩）、不用额外变量交换两个数、快速判断一个数是不是 2 的幂等等。这些技巧在竞赛中出现频率很高，值得花时间掌握。
110 就是十进制的 6。想系统复习，请回顾 2.3 节「原码反码补码」。下面表格里的每一行位运算，本质上都是把两个数按这种"位值对齐"的方式一位一位地比较。| 符号 | 名称与规则 | 记忆口诀 | 优先级 |
|---|---|---|---|
| & | 按位与（AND） 两位都为 1 才为 1，否则为 0 |
全1才1，有0出0 | 8 |
| | | 按位或（OR） 有一个 1 就为 1，全 0 才为 0 |
有1就1，全0出0 | 10 |
| ^ | 按位异或（XOR） 两位不同为 1，相同为 0 |
相同为0，不同为1 | 9 |
| ~ | 按位非（NOT） 每一位全部翻转（0→1，1→0） |
全部翻转 | 2 |
| << | 左移 所有位左移 n 位，低位补 0，相当于 ×2ⁿ |
左移 = ×2ⁿ | 5 |
| >> | 右移 所有位右移 n 位，正数高位补 0，相当于 ÷2ⁿ |
右移 = ÷2ⁿ | 5 |
7.1.1
按位与是位运算里最常用的一个。规则很直观：把两个数按位对齐，对应位只要都是 1，结果这一位才是 1，只要有一个是 0，结果就是 0。可以把它理解成"两把锁都要打开，门才能打开"——两个条件必须同时满足。
常用于：判断奇偶、检测某一位是不是 1、把某些位强制清零，是接下来几种技巧的基础。
下面是按位与最常见的四个用法。前两个是"读取"——只是看某一位是什么，不修改数据；后两个是"写入"——真正去修改数据的某些位。
| 1 | // 用途① 判断奇偶：最低位是 1 就是奇数 |
| 2 | if (n & 1) cout << "奇数"; |
| 3 | else cout << "偶数"; |
| 4 | |
| 5 | // 用途② 判断第 k 位是否为 1（k 从 0 开始，0 是最低位） |
| 6 | if ((n >> k) & 1) cout << "第k位是1"; |
| 7 | |
| 8 | // 用途③ 保留低 k 位，其余全部清零 |
| 9 | int lowK = n & ((1 << k) - 1); // (1< |
| 10 | |
| 11 | // 用途④ 将第 k 位清零，其余位保持不变 |
| 12 | n &= ~(1 << k); // ~(1< |
(1<<k)-1 和 ~(1<<k) 都属于"掩码"——一个专门构造出来、用来跟原数据做位运算的数字，作用就像一张"镂空的纸"：盖在原数据上，想保留的位置镂空露出来，不想要的位置盖住变成 0。之后处理"状态压缩"类问题时，构造合适的掩码是最核心的技巧。7.1.2
按位或的规则和按位与刚好相反：只要有一个位是 1，结果这一位就是 1，只有两个都是 0 才得 0。可以理解成"两把开关，任意一把打开，灯就亮"——只要满足其中一个条件就够了。
最常见的用途是把某一位强制设为 1，或者把多个"独立的标志位"合并成一个数字（比如文件权限里的"可读、可写、可执行"经常就是用不同的位分别表示，再用按位或拼在一起）。
| 1 | // 用途① 将第 k 位设为 1，其余位保持不变 |
| 2 | n |= (1 << k); // 1< |
| 3 | |
| 4 | // 用途② 把多个独立的标志位合并成一个数 |
| 5 | int READ = 1; // 二进制 001，第0位代表"可读" |
| 6 | int WRITE = 2; // 二进制 010，第1位代表"可写" |
| 7 | int perm = READ | WRITE; // 011，同时拥有"可读+可写"权限 |
bool 变量，权限一多就要维护一大堆变量；而用不同的二进制位分别代表一种权限，就能把好几个开关状态压缩进一个整数里存储和传递，既省空间又方便统一判断（配合按位与就能反过来查询"是否拥有某个权限"，见 7.1.1 节）。7.1.3
按位非是六个位运算符里唯一一个只需要一个操作数的（其余都要两个数才能运算），规则也最简单粗暴：把每一个二进制位全部取反，0 变 1，1 变 0，没有例外。
取反之后会出现一个有趣的规律：~n 永远等于 -(n+1)，比如 ~6 = -7、~0 = -1、~(-1) = 0。这个规律不是巧合，而是补码存储方式（见 2.3 节）决定的必然结果。
~n（全部取反）到 -n（相反数的补码）正好差一个"+1"，反过来推，~n 自然就等于 -n-1，也就是 -(n+1)。n &= ~(1 << k)。1 << k 只有第 k 位是 1，取反后 ~(1<<k) 就变成"除第 k 位是 0，其余全是 1"，和 n 做按位与，效果就是把第 k 位强制清零，其余位原样保留。这是 ~ 在实际代码里出现频率最高的用法，7.1.1 节按位与部分已经演示过。7.1.4
异或的规则和前两个刚好相反："不一样"才是 1：两位相同结果为 0，两位不同结果为 1。单看规则可能觉得平平无奇，但异或有几个非常特殊的数学性质，让它成为竞赛中出现频率最高的位运算符之一，很多"看似需要额外空间"的问题都能靠异或的性质巧妙解决。
下面这三条性质是异或所有巧妙用法的根基，建议记住并理解为什么成立——其实用"相同为0，不同为1"这条基本规则逐一代入就能推出来：
第三条性质其实是前两条的自然推论：a^b^a 因为异或满足交换律，可以先算 a^a（等于 0），再和 b 异或，也就是 0^b（等于 b）。这个"自己异或自己会抵消、和 0 异或不变"的特性，正是接下来两个技巧的原理所在。
| 1 | // 用途① 不用临时变量交换两个数 |
| 2 | a ^= b; // a 变成 a^b |
| 3 | b ^= a; // b 变成 b^(a^b) = a（原来的 a） |
| 4 | a ^= b; // a 变成 (a^b)^a = b（原来的 b），三行后两数互换 |
| 5 | |
| 6 | // 用途② 找出数组中唯一出现奇数次的数 |
| 7 | // 前提：其余每个数都恰好出现偶数次 |
| 8 | int res = 0; |
| 9 | for (int x : arr) res ^= x; // 出现偶数次的数两两抵消为 0 |
| 10 | cout << res; // 剩下的就是那个出现奇数次的数 |
光看符号推导可能有点绕，不如直接代入具体数字，一行一行地跟踪 a、b 的值是怎么变化的。设初始 a = 6、b = 3（和本节前面的例子保持一致）：
| 步骤 | 代码 | 计算过程 | a 的值 | b 的值 |
|---|---|---|---|---|
| — | 初始状态 |
— |
6 |
3 |
| ① | a ^= b |
6 ^ 3 = 5 |
5 |
3（不变） |
| ② | b ^= a |
3 ^ 5 = 6 |
5（不变） |
6 |
| ③ | a ^= b |
5 ^ 6 = 3 |
3 |
6（不变） |
b^=a 实际算的是 b^(a^b)，异或满足交换律，可以重新排列成 (b^b)^a，也就是 0^a = a——所以第②行结束后 b 就已经变成了原来的 a。第③行同理可以推出 a 变成了原来的 b。虽然节省了一个临时变量，但可读性不如直接用临时变量交换，实际工程代码中很少这样用，了解原理即可。a^a=0 而抵消成 0，对最终结果毫无影响；只有那个出现奇数次的数，抵消到最后还剩一个落单，恰好通过 a^0=a 被保留了下来。这道题是异或性质在面试和竞赛中最经典的应用之一。7.1.5
所有二进制位整体向左移动 n 位，高位丢弃，低位补 0。每左移 1 位相当于乘以 2，左移 n 位相当于乘以 2ⁿ。
可以把左移想象成"把所有数字牌一起往左推 n 格，右边空出来的位置补 0"——十进制里"在数字后面添一个 0"就是乘以 10，二进制同理，"在末尾添一个 0"就是乘以 2，这也是左移能替代乘法、并且比乘法运算更快的原因。
| 1 | 6 << 1 = 12 // 6 × 2¹ |
| 2 | 6 << 2 = 24 // 6 × 2² |
| 3 | 1 << 10 = 1024 // 2¹⁰，竞赛中极常用 |
| 4 | |
| 5 | int pow2 = 1 << k; // 快速计算 2^k |
| 6 | n |= (1 << k); // 将第 k 位设为 1 |
| 7 | |
| 8 | 1 << 31 // ⚠️ 溢出！int 最大 31 位，结果是负数 |
| 9 | 1LL << 31 // ✓ 正确：用 long long 避免溢出 |
7.1.6
所有二进制位整体向右移动 n 位，低位丢弃，正数高位补 0，负数高位补 1（算术右移，后面会详细解释）。每右移 1 位相当于除以 2 并向下取整。
右移和左移是一对镜像操作：左移是"往末尾添 0"（乘），右移则是"把末尾的位挤掉"（除）。因为整数除法本身就会自动舍弃小数部分，所以右移天然对应的是"除以 2 的幂，然后向下取整"，而不是四舍五入。
| 1 | 24 >> 1 = 12 // 24 ÷ 2 |
| 2 | 24 >> 2 = 6 // 24 ÷ 4 |
| 3 | 7 >> 1 = 3 // 7 ÷ 2 = 3.5，向下取整为 3 |
| 4 | |
| 5 | n >>= 1; // 快速除以 2（比 n/2 快） |
| 6 | int bit = (n >> k) & 1; // 取出第 k 位的值（0 或 1） |
正数右移时高位补 0，前面已经演示过。但负数右移时，C++ 采用"算术右移"（arithmetic shift）——高位补的不是 0，而是符号位本身（负数补 1），这样才能保证右移后数值仍然是负数，符合"右移等于除以 2 再向下取整"的直觉：
== 和 != 低，必须加括号：if ((n & 1) == 0) ← ✓ 正确if (n & 1 == 0) ← ✗ 错误！等价于 n & (1==0) = n & 0 = 0，永远为假！
int 是 32 位，移位不能 ≥ 32。1 << 31 会溢出（结果变负数），应改写为 1LL << 31 使用 long long。7.2
GCC 编译器提供了一套操作二进制位的内置函数，在竞赛中非常实用。以 44（二进制 101100）为例演示：
| 函数 | 功能 | 示例（x=44） | 结果 |
|---|---|---|---|
| __builtin_popcount(x) | 统计二进制中 1 的个数 | __builtin_popcount(44) | 3 |
| __builtin_clz(x) | 统计前导 0 的个数（32位） | __builtin_clz(44) | 26 |
| __builtin_ctz(x) | 统计末尾 0 的个数 | __builtin_ctz(44) | 2 |
| __builtin_ffs(x) | 最低位 1 的位置（从 1 开始计数） | __builtin_ffs(44) | 3 |
| __builtin_parity(x) | 1 的个数奇偶性（奇→1，偶→0） | __builtin_parity(44) | 1 |
| __builtin_bswap32(x) | 翻转字节序（32位大小端转换） | __builtin_bswap32(0x12345678) | 0x78563412 |
__builtin_popcount 在位集（bitmask）DP 中极常用，用来统计状态中已选了多少个元素；__builtin_ctz 可以快速找到最低位的 1（即 lowbit 操作），常见于树状数组（BIT）。对于 long long 类型，使用 __builtin_popcountll、__builtin_clzll 等带 ll 后缀的版本。7.3
把本章内容汇总成几条最容易踩坑的规则：
==、!= 等比较运算符更低，n & 1 == 0 会先算 1==0（得 false，即 0），再和 n 做按位与，结果永远是 0。判断某一位时务必加括号：(n & 1) == 0。int 是 32 位，1 << 31 及以上就会出问题（结果溢出变成负数或行为未定义）。需要更大范围时，把字面量写成 1LL << k，用 long long 参与移位。__builtin_popcount、__builtin_ctz 等函数是 GCC / Clang 的编译器扩展，标准 C++ 并未规定，MSVC 不支持这些函数名（MSVC 有功能类似但名字不同的函数，如 __popcnt、_BitScanForward）。国内 OJ 和信息学竞赛评测系统大多用 GCC，可以放心使用，但如果代码需要跨平台，或者要在 Visual Studio 里直接编译运行，这些函数会导致编译失败。&/| 是按位运算符，&&/|| 是逻辑运算符，两者名字相似但含义完全不同——按位运算符逐位计算并返回一个数值，逻辑运算符对整个表达式做真假判断并触发短路求值（见 4.1 节）。误把 if (a & b) 写成本该是 if (a && b) 的地方，即使能编译通过，结果也往往和预期不同。