第 2 章 位运算 · 知识细节练习

考点：位与 &（A1）。

解析：按位与 = 全 1 才 1：
$$1100 \& 1010 = 1000$$

✅ A。验算：$12 \& 10 = 8$ ✓（& 是逐位运算，与算术无关）。

关联 · 真值表（A1）：$1\&1=1$、$1\&0=0$、$0\&0=0$——"与 0 必得 0"，这是掩码的基础（B1）。

考点：位或 |（A2）。

解析：按位或 = 有 1 就 1：

1100 | 1010 = 1110

✅ D。验算：12 | 10 = 14 ✓。

关联 · 真值表（A2）：1 | 0 = 1、0 | 0 = 0——"或 1 必得 1"，用于强制置位（D3）。

考点：位异或 ^（A3）。

解析：按位异或 = 相同为 0、不同为 1：
$$1100 \oplus 1010 = 0110$$

✅ B。验算：$12 \oplus 10 = 6$ ✓。

关联 · 异或三性质（B3/B4）：$x\oplus0=x$、$x\oplus x=0$、可移项——这三个性质撑起了交换、找唯一元素、翻转位等所有技巧。

考点：位取反 ~（A4）。

解析：逐位取反（0↔1）：
$$\sim 0000\,0101 = 1111\,1010 = -6$$

✅ A（8 位补码视角）。~5 在 C++ 中等于 $-6$。

关联 · 取反恒等式（B5）：$\sim x = -x-1$，所以 $\sim 5 = -6$——不用展开二进制也能秒算。
关联 · 为什么是负数（F2）：补码的符号位也被取反了，正数取反必为负数。

考点：移位运算（A5）。

解析：左移 1 位 = 整体左移、低位补 0：
$$0000\,0110 \xrightarrow{<<1} 0000\,1100 = 12$$

✅ A。

关联 · 移位即乘除（C1/C2）：$x<<1 = 2x$、$x>>1 = x/2$（正整数）——比乘除法更快，编译器也会自动优化。

考点：运算符优先级（A6）。

解析：相关优先级从高到低：

<< >> → > < >= <= → == != → & → ^ → | → && → ||

<< 优先级最高。✅ C

关联 · 优先级坑（E2）：x & 1 == 0 因为 == 高于 &，实际是 x & (1==0)——写位运算表达式务必加括号，这是最高频 bug。

考点：掩码思想（B1）。

解析：x & M：$M$ 中为 $1$ 的位原样保留 $x$ 的对应位，$M$ 中为 $0$ 的位把 $x$ 清零。✅ A

关联 · 掩码的应用（B7/D2/D4）：取低 k 位 x & ((1<<k)-1)、取第 k 位 (x>>k)&1、第 k 位清零 x & ~(1<<k)——"想保留哪些位，掩码就哪些位为 1"。

考点：位运算恒等式（B2）。

解析：逐条验证：

• x | 0：或 0 不改变任何位 → x ✓
• x & 0：与 0 全部清零 → $0$，不是 $x$ ✗
• x ^ 0：异或 0 不变 → x ✓
• x ^ 1：最低位 0↔1 → 翻转 ✓

✅ B（要找的是错误的恒等式）

关联 · 记忆法：|0 不变、&0 清零、^0 不变、^1 翻转——"或保留、与清零、异或翻转"六个字。

考点：异或移项（B3）。

解析：等式两边同时异或 $a$：
$$a\oplus b = c \implies b = a\oplus b\oplus a = c\oplus a$$

✅ A。验证：$3\oplus5=6$，则 $6\oplus3 = 5$ ✓。

关联 · 异或的"逆运算是自己"（B4）：普通加法用减法移项，异或用异或自己移项——这是异或能用于加密、交换、找唯一元素的根本原因。

考点：异或运算律（B4）。

解析：异或满足交换律和结合律，且 $a\oplus a = 0$、$a\oplus 0 = a$。✅ A

关联 · 为什么重要（G2）：正是结合律 + $a\oplus a=0$，才能"把数组全部异或一遍就找出出现奇数次的元素"——成对出现的数都两两抵消了。

考点：取反恒等式（B5）。

解析：$\sim x = -x-1$ 对负数同样成立：
$$\sim(-3) = -(-3) - 1 = 3 - 1 = 2$$

✅ A。验证：$-3$ 补码 1111 1101，取反 0000 0010 = $2$ ✓。

关联 · 补码视角（F2）：$\sim x+1 = -x$（取反加一），所以 $\sim x$ 与 $-x$ 相差 $1$——两条恒等式一起记。

考点：双重取反（B6）。

解析：取反两次 = 原样还原（每一位 0↔1↔0）：
$$\sim\sim x = x$$

✅ A

关联 · 实际用途：~~x 在 JavaScript 中常用于截断小数（如 ~~3.7 = 3，先取整再还原）；C++ 中主要体现"取反是自逆运算"。

考点：取低 k 位（B7）。

解析：$(1<<4)-1 = 16-1 = 15 =$ 0000 1111（低 4 位全 1），与 $x$ 相与即保留低 4 位。✅ B

关联 · 构造掩码（C5）：(1<<k)-1 是"低 k 位全 1"的标准写法；~(1<<k) 是"除第 k 位外全 1"——这两个掩码组合能实现置位/清零/取位全部操作。

考点：左移乘 2（C1）。

解析：左移 1 位乘 $2$，左移 2 位乘 $2^2=4$：
$$3 << 2 = 3 \times 4 = 12$$

✅ A

关联 · 通用规则（C5）：x << k 等价于 $x \times 2^k$（无溢出时）；`1 << k = 2^k$——移位就是最廉价的乘 2 幂。

考点：右移除 2（C2）。

解析：正整数右移 1 位除 $2$：
$$20 >> 2 = 20 \div 4 = 5$$

✅ B

关联 · 与除法的一致性（C2）：正整数 x>>k 等于 $x \div 2^k$（整除）；负数则不同（见 C4，向负无穷取整）。

考点：逻辑右移（C3）。

解析：unsigned char 是无符号类型，右移补 0（逻辑右移）：
$$1000\,0000 \xrightarrow{>>1} 0100\,0000$$

✅ A

关联 · 算术右移对比（F3）：有符号负数右移补符号位（算术右移）：1000 0000（signed）>>1 得 1100 0000——同一串二进制，有/无符号结果不同，先看类型再移位。

考点：负数右移（C4）。

解析：$-7$ 的补码 1111 1001，算术右移补符号位：
$$1111\,1001 \xrightarrow{>>1} 1111\,1100 = -4$$

✅ A。注意 $-7 \div 2 = -3.5$，右移结果是 $-4$（向负无穷取整）。

关联 · 与正数不同（C2）：正数右移 = 整除（向 0 取整）；负数右移 = 向下取整——-7>>1 是 $-4$ 不是 $-3$，易错点。

考点：移位造幂（C5）。

解析：$1 << 5 = 2^5 = 32$。✅ A

关联 · 幂速查（C1/C5）：$1<<0=1,\ 1<<1=2,\ \dots,\ 1<<10=1024$——比查表快，且是状态压缩（G1）的基础。

考点：1<<31 溢出（C6）。

解析：$1$ 左移 31 位，唯一的 1 进入符号位：
$$1<<31 = 1000\,0000\,0000\,0000\,0000\,0000\,0000\,0000 = -2147483648$$

✅ B。$2147483648$ 超出 int 范围，结果以补码读为最小值。

关联 · 类型陷阱（H3）：同样 1<<31，unsigned int 下是 $2147483648$（无符号）——同一表达式，看类型。

考点：移出位丢失（C7）。

解析：8 位左移 4 位，高 4 位的 1111 全部移出丢失，低位补 0：
$$1111\,0000 \xrightarrow{<<4} 0000\,0000$$

✅ A

关联 · 溢出即回绕（C6）：移位不做"循环"，移出就丢；所以 $1<<31$ 的 1 会出现在符号位。

考点：奇偶判断（D1）。

解析：最低位是 $1$ 则为奇数：
$$x \& 1 = \begin{cases} 1 & x \text{ 为奇数}\\ 0 & x \text{ 为偶数}\end{cases}$$

✅ A。比 x % 2 快，且语义等价（E6）。

关联 · 取第 k 位（D2）：x & 1 就是 (x >> 0) & 1 的特例——"取最低位"是"取第 k 位"的 $k=0$ 情形。

考点：取第 k 位（D2）。

解析：先右移 $k$ 位把目标位移到最低位，再 &1：
$$(x >> 3) \& 1$$

✅ A。注意 x & 8 得到的是第 3 位的位权值（$8$ 或 $0$），不是位值（$1$ 或 $0$）。

关联 · 位权与位值（B1）：(x>>k)&1 返回 $0/1$；x&(1<<k) 返回 $0/2^k$——需要布尔判断时用前者。

考点：第 k 位设为 1（D3）。

解析："第 $2$ 位"指二进制从右往左数第 $2$ 位（位号从 $0$ 开始）：0000 0100 中为 1 的就是第 2 位。置 1 = 不管该位现在是 0 还是 1，强制变 1，其余位原样不动。

用位或（有 1 得 1）：掩码 1 << 2 = 4 = 0000 0100，只有第 2 位是 1。

第 2 位由 0 变 1，其他位没动。所以 x | (1<<2) = x | 4。✅ A

排除法：

• B x & 4：与运算不能置位，x & 4 只把结果限制在第 2 位（那是"读第 2 位"的写法）；
• C x ^ 4：异或 1 是翻转——第 2 位原本是 0 才变 1，原本是 1 会变 0，不是"置 1"；
• D x | 2：2 = 0000 0010，置的是第 1 位！位号从 0 数起，第 2 位对应 1<<2 = 4——这是最高频的坑。

关联 · 三兄弟（D3/D4/D5）：置 1 用 |、清零用 &~、翻转用 ^——对第 $k$ 位：x|(1<<k)、x&~(1<<k)、x^(1<<k)，一套背下来位操作全通。
关联 · 掩码思想（B1）：1 << k 就是"只有第 k 位为 1"的掩码；想动哪一位，掩码就哪一位为 1。

考点：第 k 位清零（D4）。

解析：~(1<<2) = ~4（除第 2 位外全 1），与 $x$ 相与即把第 2 位清零。✅ A

关联 · 掩码构造（B7）：~(1<<k) 与 (1<<k)-1 是两个基础掩码：前者"除第 k 位全 1"（清位用），后者"低 k 位全 1"（取位用）。

考点：第 k 位取反（D5）。

解析：异或 1 翻转最低位：x ^ 1。✅ A

关联 · 异或翻转（B3）：$x\oplus1$ 只改变最低位，其他位不变——因为 $b\oplus0=b$。
关联 · 大小写（D10）：ch ^ 32 就是在翻转 ASCII 码的第 5 位，实现大小写切换。

考点：异或交换（D6）。

解析：三步推导（$a_0=5,b_0=6$）：

1. $a_1 = a_0\oplus b_0 = 3$
2. $b_1 = b_0\oplus a_1 = 6\oplus3 = 5$（= 原 $a_0$）
3. $a_2 = a_1\oplus b_1 = 3\oplus5 = 6$（= 原 $b_0$）

✅ A：$a=6$、$b=5$，完成交换。

关联 · 陷阱（H2）：若 $a$、$b$ 是同一变量（如 swap(a,a)），三步后都变 $0$——异或交换不能用于同变量。
关联 · 原理（B3/B4）：本质是"用异或存两数差异，再逐步还原"。

考点：lowbit（D7）。

解析：$x\&-x$ 保留 $x$ 最低位的 $1$ 及其后的 0：
$$12 \& (-12) = 1100 \& 0100 = 0100 = 4$$

✅ A。原理：$-x = \sim x + 1$，取反后最低位 1 以上的位全变，& 后只剩最低位 1。

关联 · 树状数组（G5）：lowbit 是树状数组的核心操作；配合 x&(x-1)（去最低位 1）可以遍历所有 1 的位置。

考点：判断 2 的幂（D8）。

解析：$x$ 是 2 的幂 ⇔ 二进制只有一个 1 ⇔ 去掉最低位 1 后为 0：
$$(x \& (x-1)) == 0$$

✅ A。注意 B 选项 x & (x-1) == 0 是陷阱：== 优先级高于 &，它等价于 x & ((x-1)==0)，几乎恒为 0——优先级坑（E2）的现场版。

关联 · 去最低位 1（D9）：x&(x-1) 是把最低位的 1 变成 0，2 的幂只有一个 1，所以结果为 0。

考点：去掉最低位的 1（D9）。

解析：$x-1$ 会把最低位 1 变成 0、其后的 0 全变 1：
$$14 \& 13 = 1110 \& 1101 = 1100 = 12$$

✅ A

关联 · 数 1 的个数（E4/G4）：反复执行 n &= n-1 直到 0，执行的次数就是 1 的个数——经典循环。

考点：大小写切换（D10）。

解析：大小写 ASCII 相差 $32 = 2^5$，即只差第 5 位：
$$\text{'A'}(65) \oplus 32 = 97 = \text{'a'}$$

✅ A。ch ^ 32 切换大小写；ch | 32 强制小写；ch & ~32 强制大写。

关联 · ASCII 表（第 1 章 F2）：'A'=65、'a'=97、差 32——位运算视角下，大小写转换就是翻转/置位第 5 位。

考点：混合位运算优先级（E1）。

解析：& 高于 ^，先算与、再算异或：

6 & 3 = 2，2 ^ 5 = 7

✅ A

关联 · 优先级全序（A6）：<< >> → == → & → ^ → | → &&（从高到低）——混合位运算先按优先级分组，拿不准就加括号。

考点：优先级坑（E2）。

解析：== 优先级高于 &，所以：
$$x \& 1 == 0 \implies x \& (1==0) = 3 \& 0 = 0$$

✅ A。本意"判断 $x$ 的末位是否为 0"应写 (x & 1) == 0。

关联 · 经典 bug（A6）：if (x & 1 == 0) 这类写法在真实代码里会造成"条件恒假/恒真"——位运算表达式一律加括号。

考点：负数位运算（E3）。

解析：负数按补码参与位运算：
$$-6 = 1111\,1010,\qquad 3 = 0000\,0011 \implies -6 \& 3 = 0000\,0010 = 2$$

✅ A

关联 · 补码视角（第 1 章 D4）：位运算是按存储的补码逐位进行的，与"真值"无关——所以 -6 & 3 得正数 $2$，直觉"负数与正数"没用，展开补码才算得准。

考点：程序阅读（E4）。

解析：循环体 n &= n-1 每次去掉一个最低位的 1（D9）：
$$12 = 1100 \to 1000 \to 0000$$

去掉了 $2$ 个 1 → cnt = 2。✅ A

关联 · 数 1 模板（G4）：while(n){ n&=n-1; cnt++; } 是"数二进制中 1 的个数"的经典写法，比逐位移位快（循环次数 = 1 的个数）。

考点：lowbit 与去位组合（E5）。

解析：$24 = 11000$：

• n & -n：最低位 1 在第 3 位 → $1000 = 8$
• n & (n-1)：去掉最低位 1 → $10000 = 16$

✅ A（$8$ 与 $16$）

关联 · 一对互补操作（D7/D9）：x&-x 取出最低位 1；x&(x-1) 去掉最低位 1——一个"取"一个"删"，配合使用可以遍历 $x$ 的所有 1 位。

考点：n&1 与 n%2（E6）。

解析：对非负整数，最低位为 1 ⇔ 奇数：
$$n \& 1 \equiv n \% 2$$

✅ A。位运算省去除法，通常更快（现代编译器也会把 n%2 优化成 n&1）。

关联 · 负数例外（E3）：C++ 中 -3 % 2 = -1 而 -3 & 1 = 1——负数时两者不等！题目限定"非负整数"就是这个原因。

考点：负数取反（F1）。

解析：$-6$ 补码 1111 1010 逐位取反：
$$\sim 1111\,1010 = 0000\,0101 = 5$$

✅ A。与恒等式验证一致：$\sim(-6) = -(-6)-1 = 5$。

关联 · 正负交替规律（B5）：$\sim 5 = -6$、$\sim(-6) = 5$——取反在"相邻正负数"之间跳：$x \leftrightarrow -x-1$。

考点：取反加一（F2）。

解析：$-x = \sim x + 1$：
$$\sim 0000\,0101 = 1111\,1010,\qquad +1 = 1111\,1011 = -5$$

✅ A。验证：$1111\,1011$ 读补码 $= -5$ ✓。

关联 · 求相反数模板（B5）：-x 的位运算写法就是 ~x + 1——这也是"$-x = \sim x + 1$"与"$\sim x = -x-1$"互推的原因。

考点：负数算术右移（F3）。

解析：$-3$ 补码 1111 1101，算术右移补符号位：
$$1111\,1101 \xrightarrow{>>1} 1111\,1110 = -2$$

✅ A（GESP 真题原题数值）

关联 · 向负无穷取整（C4）：$-3 \div 2 = -1.5$，右移结果 $-2$——算术右移对负数就是向下取整，与正数不同。

考点：符号位提取（F4）。

解析：负数算术右移 31 位，符号位 $1$ 被复制到所有位：
$$x >> 31 = 1111\,1111\,1111\,1111\,1111\,1111\,1111\,1111 = -1$$

✅ A。正数时 x>>31 得 $0$——所以 x>>31 是"负数判据"：$0$ 或 $-1$。

关联 · 绝对值技巧（F5）：正是 x>>31 只在负数时为 $-1$，才有了"无分支绝对值"公式。

考点：绝对值技巧（F5）。

解析：$x=-5$：

• $x>>31 = -1$（F4）
• $x \oplus (-1) = \sim x = 4$（异或全 1 = 取反）
• $4 - (-1) = 5$ ✅ A

原理：$x\ge0$ 时 $x>>31=0$，结果 $x$；$x<0$ 时先取反再 $+1$（$-x$ 的过程），即 $\sim x - (-1) = \sim x + 1 = -x$。

关联 · 无分支思想：没有 if 也完成绝对值——位运算常用于消除分支、加速热点代码。

考点：状态压缩（G1）。

解析：元素 $i$ 对应第 $i$ 位，插入 = 置 1：

s = s | (1 << 3)（等价于 s |= 1 << 3）

✅ A。注意 s |= 3 会同时置第 0、1 位，不是"插入元素 3"。

关联 · 压缩全集（C5）：$n$ 个元素的集合全集 = (1<<n)-1；删除元素 s &= ~(1<<i)；判断存在 (s>>i)&1——位集三件套。

考点：异或找唯一（G2）。

解析：异或满足交换律结合律，成对元素两两抵消：
$$3 \oplus 5 \oplus 3 \oplus 7 \oplus 5 = (3\oplus3) \oplus (5\oplus5) \oplus 7 = 0 \oplus 0 \oplus 7 = 7$$

✅ A

关联 · 原理（B3/B4）：$a\oplus a = 0$、$0\oplus x = x$——数组全部异或，唯一出现奇数次的元素胜出。这是"不用额外空间找唯一"的经典解法。

考点：集合位运算（G3）。

解析：交集 = 两边都为 1 的位 = 按位与：
$$A \cap B \iff A \& B$$

✅ A。并集 A|B、对称差 A^B、补集 ~A。

关联 · 集合模板（G1）：位集把集合运算变成一条位运算指令——$O(1)$ 时间完成交并补，这是状态压缩的核心优势。

考点：统计 1 的个数（G4）。

解析：$29 = 11101$，逐位统计：
$$11101 = 1+1+1+0+1 \to 4 \text{ 个 } 1$$

✅ A

关联 · 两种数法（E4）：逐位移位 cnt += (x>>i)&1 固定循环 32 次；while(x){x&=x-1;cnt++;} 只循环"1 的个数"次——后者更快。

考点：lowbit 应用（G5）。

解析：$40 = 101000$，最低位 1 在第 3 位：
$$\text{lowbit}(40) = 40 \& (-40) = 101000 \& 011000 = 001000 = 8$$

✅ A

关联 · 树状数组（D7）：树状数组的更新与查询都靠 lowbit 跳步：i += lowbit(i) 向上、i -= lowbit(i) 向下——lowbit 是它的心脏。

考点：&& 与 &（H1）。

解析：& 对每一位做逻辑与（返回整数）；&& 是逻辑与（返回 $0/1$）且短路——左边为假就不算右边。✅ A

关联 · 短路副作用：if (p && *p) 安全（p 为空则不解引用）；if (p & *p) 会先算两边——空指针直接崩。写法混用是经典 bug 源。

考点：同变量异或（H2）。

解析：$a \oplus a = 0$：
$$a \verb|^=| a \implies a = 5 \oplus 5 = 0$$

✅ A。同理，异或交换若两个"变量"实际指向同一块内存（如 swap(a[i], a[j]) 且 $i=j$），结果会把那个值清零。

关联 · 交换注意（D6）：异或交换省内存但要求两变量确实不同；常规 swap 用临时变量则没有这个限制——写代码时优先临时变量。

考点：1<<31 无符号视角（H3）。

解析：unsigned int 无符号位，1<<31 的最高位就是普通数值位：
$$1<<31 = 1000\,0000\,0000\,0000\,0000\,0000\,0000\,0000 = 2^{31} = 2147483648$$

✅ A。同一表达式：有符号得 $-2147483648$（C6），无符号得 $2147483648$。

关联 · 类型决定读法（C6/F4）：二进制串本身没有正负，是"类型"决定按补码还是按无符号读——1<<31 两问两答案，考的就是这个。

考点：负数左移 UB（H4）。

解析：C++ 标准规定：对负数左移（如 -1 << 1）是未定义行为（UB）。✅ A

关联 · 右移的待遇（C4/F3）：负数右移是 implementation-defined（绝大多数编译器做算术右移，结果可预期）；负数左移连"实现定义"都不是——标准直接不保证。写代码别依赖它。