位运算技巧

第 0 步：为什么值得专门学一课位运算？

CSP-J 初赛几乎每年都考位运算：2021 年一套阅读程序连出 5 题（数 1 的个数、取最低位的 1、Base64 拆比特），2022 年考比特交织，2025 年又考了 x&(x-1)。

位运算常被当成"背套路"，其实它是可以系统学会的一门小语言：6 个运算符 + 3 个经典套路，就能覆盖初赛绝大多数位运算题。

本篇安排在《基本运算与位运算》真题练习之前——先把工具磨快，再去砍真题。

学习方法只有一条：每学一个技巧，就在草稿纸上列竖式亲手算一遍，然后立刻做随堂练习。位运算的手感 = 你手算过的例子数。

第 1 步：二进制快速回顾

二进制的第 k 位（从 0 开始数）代表 2^k，这叫"位权"。把每一位乘以位权再相加，就得到十进制值。

13 = 8 + 4 + 1：

位权:  8 4 2 1
数字:  1 1 0 1

十进制转二进制：不断减去"还能减的最大的 2 的幂"。45 = 32 + 8 + 4 + 1：

位权: 32 16 8 4 2 1
取值:  1  0 1 1 0 1

所以 45 = 101101(2)。

C++ 里可以直接写二进制字面量：int x = 0b101101;（C++14 起）。位权 2^k 是后面所有内容的地基，务必反应够快。

【随堂练习 1】把二进制数 101101 换算成十进制，结果是。

第 2 步：三兄弟 &、|、^（按位运算）

这三个运算符对两个整数的每一个二进制位独立运算，互不干扰、永不进位：

&（与）：两位都是 1 才得 1
|（或）：至少一位是 1 就得 1
^（异或）：两位不同才得 1（相同得 0）

竖式演算 13 和 11（逐位对齐）：

  1 1 0 1   (13)
& 1 0 1 1   (11)
---------
  1 0 0 1   (9)

  1 1 0 1   (13)
| 1 0 1 1   (11)
---------
  1 1 1 1   (15)

  1 1 0 1   (13)
^ 1 0 1 1   (11)
---------
  0 1 1 0   (6)

记忆法：^ 就是"不进位加法"——每位 1+1 本该进位，异或直接得 0，把进位扔掉了。

【随堂练习 2】计算 13 ^ 11 的值。

第 3 步：取反 ~ 与补码

int 里的负数用"补码"存储，规则只有一条：-x = ~x + 1（取反加一）。反过来得到推论：~x = -x - 1。

用 8 位看 x = 5：

  x  = 00000101   (5)
  ~x = 11111010   (-6)
x+~x = 11111111   (-1)

x 和 ~~x 每一位都相反，相加每位都是 1，也就是 -1。所以 ~5 = -6、~~12 = -13、~0 = -1——这些不用背，记住"x + ~x = -1"就能现推。

补码马上会立大功：它是后面"魔法二 x & -x"的原理。

【随堂练习 3】在 C++ 中，表达式 ~12 的值是。

第 4 步：移位 = 最快的乘除法

左移 x << k：整体左移 k 位，低位补 0，等于乘 2^k。
右移 x >> k：整体右移 k 位，等于除以 2^k 并向下取整。

5  << 2: 0000101 -> 0010100  (20)
19 >> 2: 0010011 -> 0000100  (4，因为 19/4=4.75 取 4)

最重要的推论：1 << n 就是 2^n。1<<0=1、1<<3=8、1<<10=1024。2019 年"矩阵变幻"真题里 int size = 1 << n; 考的就是它。

第二个基本功：n & 1 判断奇偶——最低位是 1 就是奇数。7 & 1 = 1（奇），10 & 1 = 0（偶）。比 n % 2 更快，也是位运算版的"看个位数"。

【随堂练习 4】填空：1 << 5 = ；19 >> 3 = ；9 & 1 = 。

第 5 步：对第 k 位的"四式"（背下来）

约定：k 从 0 数，最低位是第 0 位。1 << k 只有一个 1，像一枚"第 k 位专用开关"：

(n >> k) & 1      // 查：第 k 位是 0 还是 1
n | (1 << k)      // 置：把第 k 位变成 1
n & ~(1 << k)     // 清：把第 k 位变成 0
n ^ (1 << k)      // 翻：把第 k 位翻转

以 n = 13 = 1101(2)、k = 1（第 1 位是 0）为例：

查：(13 >> 1) & 1 = 110 & 1 = 0
置：13 | 2 = 1111 = 15
清：13 & ~1 = 1101 & 1110 = 1100 = 12
翻：13 ^ 2 = 1111 = 15

置、清、翻都不影响其他位：开关里只有第 k 位是 1，其余位 & 上原值、| 上 0、^ 上 0，纹丝不动。

【随堂练习 5】设 n = 22（二进制 10110），表达式 (n >> 2) & 1 的值是？

第 6 步：魔法一 x & (x-1)，消去最低位的 1

x - 1 会发生"借位"：x 最低位的 1 变成 0，它右边的所有 0 变成 1，左边原样不动。于是 x 和 x-1 只有"最低位 1 及其右边"不同——拿 & 一夹，右边全清零、左边全保留：

结果 = x 去掉最低位的那个 1。

  x   = 1 1 0 0   (12)
  x-1 = 1 0 1 1   (11)
  & -------------
        1 0 0 0   (8)

12 的最低位 1 在第 2 位（值 4），消掉后只剩 8。

2025 年初赛直接考了它：255 & 254 = 11111111 & 11111110 = 11111110 = 254。这个技巧是后面两个大招的地基。

【随堂练习 6】计算 40 & 39 的值

第 7 步：数 1 的个数（popcount）与判断 2 的幂

x & (x-1) 每执行一次消掉一个 1，那么执行几次能变 0，x 里就有几个 1（Brian Kernighan 法）：

int popcount(int x) {
    int c = 0;
    for (; x; x &= x - 1) c++;
    return c;
}

2021 年真题的数据 511998 = 1111100111111111110(2)，反复消 1：

511998 -> 511996 -> 511992 -> 511984 -> ... -> 262144 -> 0

共 16 步，所以 popcount(511998) = 16。

判断 2 的幂：2 的幂二进制里只有一个 1，消掉它就归零。64 & 63 = 1000000 & 0111111 = 0，是；96 & 95 = 1100000 & 1011111 = 1000000 = 64，不是。

【随堂练习 7】执行以下程序片段后，c 的值是。

int x = 84, c = 0;
for (; x; x &= x - 1) c++;

第 8 步：魔法二 x & -x，取出最低位的 1

补码派上用场了。-x = ~~x + 1：~~x 让高位全部翻转，而 +1 的借位恰好把低位翻回原样、在最低位的 1 下面停住。于是 x & -x 里只有 x 最低位的 1 幸存，其余位全被 & 成 0。

  x  = 00001100   (12)
  ~x = 11110011
  -x = 11110100   (~x 加 1)

x & -x:
  00001100
& 11110100
---------
  00000100   (4)

这个结果有个名字：lowbit(x)。

2021 年真题 g(x) = x & -x，还和 popcount 打组合拳：输入 10 = 1010(2) 时输出 popcount + lowbit = 2 + 2 = 4（原题故意写 5 骗人）。511998 & -511998 = 2。lowbit 也是以后"树状数组"的核心零件。

【随堂练习 8】计算 44 & -44 的值。

第 9 步：异或专题（一）：三条铁律

a ^ a = 0（自己和每一位都相同，全得 0）
a ^ 0 = a（和 0 异或，原样不动）
交换律、结合律：一长串异或随便调换顺序、随便加括号

  1 0 1 1   (11)
^ 1 0 1 1   (11)
-----------
  0 0 0 0   (0)

最重要的推论：a ^ b ^ b = a——同一个数异或两次，等于没异或。

所以一长串异或的结果，只取决于每个数出现奇数次还是偶数次：偶数次的全部自我抵消，只剩下奇数次的。这条推论直接催生下一张卡的三个应用。

第 10 步：异或专题（二）：三个必会应用

① 找落单的数：其他数都出现两次、只有一个数出现一次？全员异或，成对的全抵消：

int ans = 0;
for (int i = 0; i < n; i++) ans ^= a[i];

② 三连交换：不用临时变量交换两个整数：

a ^= b;  // a = 原a ^ 原b
b ^= a;  // b = 原b ^ 原a ^ 原b = 原a
a ^= b;  // a = 原a ^ 原b ^ 原a = 原b

③ 0/1 翻转开关：p ^= 1 让 p 在 0 和 1 之间跳（0^1=1，1^1=0）。2021 年约瑟夫问题真题里，报数方向交替切换用的就是它。

这三个应用的根都是同一条：异或两次等于没异或。

【随堂练习 9】数组 a = {4, 9, 4, 11, 9}，把所有元素异或起来（4 ^ 9 ^ 4 ^ 11 ^ 9），结果是。

第 11 步：掩码——像拼积木一样拆拼比特

掩码（mask）：一个精心设计的 0/1 串，用 & 把不要的位清掉。三个常客建议背下来（0x 前缀表示十六进制）：

0x0f = 00001111   只留低 4 位
0x33 = 00110011   留第 0、1、4、5 位
0x55 = 01010101   留第 0、2、4、6 位（偶数位）

更通用的写法：x & ((1 << k) - 1) 保留低 k 位；x & ~((1 << k) - 1) 清掉低 k 位。

拆拼套路 = 掩码筛选 + 移位搬运 + | 拼接。2021 年 Base64 真题就是把 4 个 6 比特重组为 3 个字节：

ret += (a & 0x0f) << 4 | b >> 2;
// (a & 0x0f) << 4：留 a 的低 4 位，搬到字节上半
// b >> 2：把 b 的高 4 位挪到下半
// |：上下拼成一个完整字节

【随堂练习 10】设 a = 178，b = 41，计算表达式 ((a & 0x0f) << 4) | (b >> 2) 的值。

第 12 步：难点攻坚——比特交织（2022 年真题）

目标：把 x 的第 i 位搬到结果的第 2i 位（中间空出的位置留给另一个数）。两步魔法：

x = (x | x << 2) & 0x33;   // 先拉开 2 格
x = (x | x << 1) & 0x55;   // 再拉开 1 格

手推 x = 13 = 1101(2)：

x          = 00001101   (13)
x | x<<2   = 00111101   13 和 13<<2 的 1 合并
& 0x33     = 00110001   (49)   只留第 0、1、4、5 位
x | x<<1   = 01110011   (115)  49 和 49<<1 的 1 合并
& 0x55     = 01010001   (81)   只留第 0、2、4、6 位

13 的第 0、2、3 位 -> 结果的第 0、4、6 位：81 = 64 + 16 + 1。同理 8 = 1000(2) -> 01000000(2) = 64。

最后 z = x | y << 1 把 y 整体挪到奇数位：81 | 64 << 1 = 81 | 128 = 11010001(2) = 209。这就是 2022 年那道"比特交织"真题的谜底——拆开看不过是掩码加移位。

【随堂练习 11】运行下面的交织程序（改编自真题思想，注意最后一行谁在奇数位），输入 5 3，输出的 z 是。

unsigned short x, y;
cin >> x >> y;
x = (x | x << 2) & 0x33;
x = (x | x << 1) & 0x55;
y = (y | y << 2) & 0x33;
y = (y | y << 1) & 0x55;
unsigned short z = y | x << 1;
cout << z << endl;

第 13 步：小盒子截断——char 只有 8 位

每种类型就是一个固定大小的盒子：char 装 8 位，unsigned short 装 16 位，int 装 32 位。往小盒子里塞大数，高位直接丢弃，相当于自动做了 & 0xFF（或 & 0xFFFF）。

2021 年 Base64 真题里，查表得到的两个 6 比特索引 13 和 49 拼第三个字节：13 << 6 | 49 = 881，装进 char 之后：

881       = 0000 0011 0111 0001
只留低 8 位 -> 0111 0001 = 113

113 恰好是字符 'q' 的 ASCII 码——很多人比特全算对，最后栽在截断上。

再如 unsigned char c = 300; 会得到 44（300 = 0000 0001 0010 1100，留低 8 位）。

读程序题看到 char / short，先问一句：盒子装得下吗？

第 14 步：优先级大坑——先括号，保平安

位运算优先级从高到低：~ > 移位 > & > ^ > |。最致命的是：&、^、| 这三个全都低于 ==！而且 ~ 和移位反而高于 ==，所以 1 << 2 == 4 会先算移位再比较，这里括号能省；但 n & 1 == 0 这种就一定要写 (n & 1) == 0。

所以 n & 1 == 0 不是"n 是偶数"。它被编译器理解为 n & (1 == 0)，也就是 n & 0，无论 n 是多少，结果恒为 0（假）——条件永远不成立，还不报任何错。正确写法：

if ((n & 1) == 0) { /* ... */ }   // 括号，永远的神

另外两个坑：

1LL << k：int 只有 32 位，1 << 40 是未定义行为；要移超过 31 位，必须写 1LL << 40。
负数右移在 C++20 里才被标准规定为算术右移（高位补符号位 1），更早的标准里这是"由实现定义"——不过主流编译器（NOI 系评测机）实际都是算术右移。初赛读到"负数 >> k"要多留个心眼。

铁律：位运算表达式里，能加括号就加括号。

【随堂练习 12】C++ 中，表达式 n & 1 == 0 的值是？

n 为偶数时为 1，奇数时为 0

n 为奇数时为 1，偶数时为 0

恒为 0

恒为 1

第 15 步：&& 和 & 是两回事（衔接下一篇）

两组符号长得很像，但完全是两种运算：

& | ^ ~（按位）：对两个整数的每一位独立运算，结果是整数，没有短路。
&& || !（逻辑）：把操作数当真假（非 0 即真），结果是 1 或 0，有短路——左边已能决定结果时，右边根本不会执行。

12 && 5 -> 1    （两个都非 0，逻辑真，值为 1）
12 &  5 -> 4    （1100 & 0101 = 0100，按位算）

短路正是 2022 年复赛《逻辑表达式》的主角：0 && f() 不会调用 f()，1 || f() 也不会——那道题还要统计短路发生了几次。优先级上两组一一对应：& 高于 |，&& 也高于 ||。而且 &&、|| 比所有位运算都低——所以 a & b && c 会先算 a & b。老规矩：能加括号就加括号。

下一篇《基本运算与位运算》的真题里，逻辑运算和位运算会同台出现，先把这层区别刻进脑子。

【随堂练习 13】表达式 (10 && 3) 与 (10 & 3) 的值分别是？

1 和 2

1 和 1

10 和 3

2 和 1

【课后作业 1/6】把十进制数 2026 转换成二进制，结果是（直接写 0/1 串，不含前缀）。

【课后作业 2/6】执行 int x = 200, c = 0; for (; x; x &= x - 1) c++; 之后，c 的值是。

【课后作业 3/6】判断正整数 n 是不是 2 的幂，下列表达式正确的是？

n % 2 == 0

n > 0 && (n & (n - 1)) == 0

n & 1 == 0

(n & (n - 1)) == 0

【课后作业 4/6】数组 {13, 5, 13, 8, 5} 中，其他数都出现两次，只有一个数落单。把所有元素异或起来，结果是，它就是落单的数。

【课后作业 5/6】执行 unsigned char c = 511; 之后，c 的值是？

511

255

127

256

【课后作业 6/6】编写完整 C++ 程序：读入一个正整数 n（n 不超过 10^9），输出两行——第一行是 n 的二进制中 1 的个数，第二行是 n 的最低位 1 所代表的值（lowbit）。写完代码后，说明你用到了本篇的哪两个技巧，以及它们各自的原理。

总结地图：你已经集齐全部装备

地基：二进制位权 -> 6 个运算符 -> 补码（~x = -x - 1）
基本功：n & 1 判奇偶、1 << n = 2^n、移位即乘除、第 k 位四式（查/置/清/翻）
两大魔法：x & (x-1) 消最低位 1（popcount、判 2 的幂）；x & -x 取最低位 1（lowbit）
异或：a ^ a = 0、找落单、三连交换、p ^= 1 翻转开关
拆拼：掩码 0x0f / 0x33 / 0x55 + 移位拼接（Base64）、比特交织、char/short 截断
防坑：优先级加括号、1LL << k、负数右移、&& 与 & 的区别

把作业写完，下一篇《基本运算与位运算》真题见。

尾声：下一步去哪

以后会学到，先混个眼熟：

for (s = (s - 1) & m; s; ) 枚举子集——状态压缩 DP 的钥匙；__builtin_popcount(x) 和 __builtin_ctz(x)——GCC 内置函数直接数 1、找最低位 1 的位置；还有趣味的大小写转换：ch | ' ' 转小写、ch & '_' 转大写（置位/清零 ASCII 第 5 位：| 把它变成 1，& 把它变成 0，真要"翻转"得用 ^）。

把作业写完，下一篇《基本运算与位运算》真题见。