C++ 编程语法

七、位运算

位运算直接操作二进制位，速度极快（比乘除法快得多），是竞赛编程的核心技巧。所有位运算都针对补码进行。

7.1

六大位运算符总览

位运算直接操作整数的二进制位。C++ 提供六个位运算符，各有特定的运算规则与优先级：

符号名称与规则记忆口诀优先级
&
按位与（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

& 按位与（AND）

对应位都为 1 时结果才为 1，否则为 0。常用于：判断奇偶、检测某位、清零某些位。

&
6 & 3 = 2
规则：1&1=1  ·  1&0=0  ·  0&0=0
 
0
0
0
0
0
1
1
0
(6)
&
0
0
0
0
0
0
1
1
(3)
=
0
0
0
0
0
0
1
0
(2) ✓
🔍 判断奇偶
if (n & 1) // 最低位=1 → 奇数 cout << "奇数"; else cout << "偶数";
🎯 判断第 k 位是否为 1
if ((n >> k) & 1) cout << "第k位是1"; // k 从 0 开始，0 是最低位
🧹 保留低 k 位
int lowK = n & ((1 << k) - 1); // (1<
🚿 将第 k 位清零
n &= ~(1 << k); // ~(1<

7.1.2

| 按位或（OR）

只要有一个位为 1 结果就为 1，全 0 才得 0。常用于：将某些位强制设为 1、合并标志位。

|
6 | 3 = 7
规则：1|1=1  ·  1|0=1  ·  0|0=0
 
0
0
0
0
0
1
1
0
(6)
|
0
0
0
0
0
0
1
1
(3)
=
0
0
0
0
0
1
1
1
(7) ✓
C++ · 按位或用途
1// 将第 k 位设为 1
2n |= (1 << k); // 1<

7.1.3

~ 按位非（NOT）

将每一个二进制位全部取反（0→1，1→0）。重要规律：~n = -(n+1)，例如 ~6 = -7，~0 = -1，~(-1) = 0。

~
~6 = -7
规则：~1=0  ·  ~0=1  （全部翻转）
~
0
0
0
0
0
1
1
0
(6)
=
1
1
1
1
1
0
0
1
(-7，补码) ✓
💡
配合 & 清零某位：n &= ~(1 << k) — ~(1<<k) 除第 k 位是 0 外其余全是 1，按位与后第 k 位清零，其余位保持不变。

7.1.4

^ 按位异或（XOR）

两位相同结果为 0，两位不同结果为 1。异或有非常神奇的性质，是竞赛中最常用的位运算之一。

^
6 ^ 3 = 5
规则：1^1=0  ·  1^0=1  ·  0^0=0
 
0
0
0
0
0
1
1
0
(6)
^
0
0
0
0
0
0
1
1
(3)
=
0
0
0
0
0
1
0
1
(5) ✓

异或的三个神奇性质

a ^ a == 0
任何数与自己异或得 0
a ^ 0 == a
任何数与 0 异或得本身
a^b^a == b
满足交换律和结合律
🔄 不用临时变量交换两数
a ^= b; b ^= a; a ^= b; // 三步后 a、b 互换
🔍 找出唯一出现奇数次的数
int res = 0; for (int x : arr) res ^= x; // 偶数次→0，奇数次留下 cout << res;

7.1.5

<< 左移

所有二进制位整体向左移动 n 位，高位丢弃，低位补 0。每左移 1 位相当于乘以 2，左移 n 位相当于乘以 2ⁿ。

6 << 2 = 24（6 × 2² = 6 × 4）
原始 (6)
0
0
0
0
0
0
1
1
0
↙↙ 左移 2 位，右侧补 00
结果 (24)
0
0
0
1
1
0
0
0
= 16+8 = 24 ✓
C++ · 左移常见用途
16 << 1 = 12 // 6 × 2¹
26 << 2 = 24 // 6 × 2²
31 << 10 = 1024 // 2¹⁰，竞赛中极常用
4
5int pow2 = 1 << k; // 快速计算 2^k
6n |= (1 << k); // 将第 k 位设为 1
7
81 << 31 // ⚠️ 溢出！int 最大 31 位，结果是负数
91LL << 31 // ✓ 正确：用 long long 避免溢出

7.1.6

>> 右移

所有二进制位整体向右移动 n 位，低位丢弃，正数高位补 0，负数高位补 1（算术右移）。每右移 1 位相当于除以 2 并向下取整。

24 >> 2 = 6（24 ÷ 2² = 24 ÷ 4）
原始 (24)
0
0
0
1
1
0
0
0
↘↘ 右移 2 位，低位丢弃，左侧补 00
结果 (6)
0
0
0
0
0
1
1
0
= 4+2 = 6 ✓
C++ · 右移常见用途
124 >> 1 = 12 // 24 ÷ 2
224 >> 2 = 6 // 24 ÷ 4
37 >> 1 = 3 // 7 ÷ 2 = 3.5，向下取整为 3
4
5n >>= 1; // 快速除以 2（比 n/2 快）
6int bit = (n >> k) & 1; // 取出第 k 位的值（0 或 1）
🚨
优先级陷阱！位运算的优先级比 == 和 != 低，必须加括号：
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 二进制内置函数速查

GCC 编译器提供了一套操作二进制位的内置函数，在竞赛中非常实用。以 44（二进制 101100）为例演示：

44 = 0000 0000 0000 0000 0000 0000 0010 1100（32位）
0
0
0
0
0
0
0
0
·
0
0
0
0
0
0
0
0
·
0
0
0
0
0
0
0
0
·
1
0
1
1
0
0
■ = 值为1的位（共3个）    ■ = 末尾0（共2个）
函数功能示例（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 后缀的版本。