# 3.2 二进制运算 --- ## 一、为什么还要学“二进制运算”？ 在上一节里，我们已经知道了计算机用二进制存数，也知道了补码能把减法变成加法。接下来要学的是： - 按位与（AND） - 按位或（OR） - 按位非（NOT） - 按位异或（XOR） - 左移（`<<`） - 右移（`>>`） - 二进制加法 - 二进制减法 这些运算不是“冷知识”，而是程序里常见的底层工具：权限开关、状态压缩、快速比较、数据校验都会用到。 --- ## 二、先记住 6 个位运算 设两个二进制位分别是 $a$ 和 $b$，每一位只可能是 0 或 1。 ### 1. 按位与 AND（符号 `&`） 规则：只有两位都为 1，结果才是 1。 | a | b | a & b | |:---:|:---:|:-----:| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | 可以理解为“都同意才通过”。 ### 2. 按位或 OR（符号 `|`） 规则：只要有一位是 1，结果就是 1。 | a | b | a \| b | |:---:|:---:|:------:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 | 可以理解为“有人同意就通过”。 ### 3. 按位非 NOT（符号 `~`，一元运算） 规则：0 变 1，1 变 0。 | a | ~a | |:---:|:---:| | 0 | 1 | | 1 | 0 | ### 4. 按位异或 XOR（符号 `^`） 规则：两位不同为 1，相同为 0。 | a | b | a ^ b | |:---:|:---:|:-----:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | 可以理解为“不同就亮灯”。 ### 5. 左移（符号 `<<`） 规则：`x << k` 表示所有位向左移动 $k$ 位，右侧补 0。 - 在不溢出的情况下，数值相当于乘 $2^k$。 - 固定 32 位时，左边移出去的高位会被丢弃。 例：8 位下 `00101101 << 2 = 10110100`。 ### 6. 右移（符号 `>>`） 规则：`x >> k` 表示所有位向右移动 $k$ 位。 - 对无符号数，左侧补 0。 - 对有符号数，很多语言会做“算术右移”（补符号位），所以课堂里先按无符号来理解更稳妥。 例：8 位下 `00101101 >> 3 = 00000101`。 --- ## 三、C++ 里位运算的优先级（一定要加括号） 下面按 cppreference 的顺序，只保留“和计算最相关”的部分（第 5-7、9-15 级）： | 优先级（高 -> 低） | 运算符 | 含义 | | |:-----------:|:----------------- |:----- |:---:| | 5 | `*` `/` `%` | 乘、除、模 | | | 6 | `+` `-` | 加、减 | | | 7 | `<<` `>>` | 左移、右移 | | | 9 | `<` `<=` `>` `>=` | 关系比较 | | | 10 | `==` `!=` | 相等比较 | | | 11 | `&` | 按位与 | | | 12 | `^` | 按位异或 | | | 13 | `\|` | 按位或 | | | 14 | `&&` | 逻辑与 | | | 15 | `\|\|` | 逻辑或 | | 看 5 个典型例子： 1) `a + b << 1` - 实际等价于 `(a + b) << 1` - 不是 `a + (b << 1)` 2) `x | y & z` - 实际等价于 `x | (y & z)` - 不是 `(x | y) & z` 3) `a ^ b & c` - 实际等价于 `a ^ (b & c)` - 不是 `(a ^ b) & c` 4) `x + y > z` - 实际等价于 `(x + y) > z` - 不是 `x + (y > z)` 5) `a & b == 0` - 实际等价于 `a & (b == 0)`（因为 `==` 高于 `&`） - 想判断“按位与结果是否为 0”，应写成 `(a & b) == 0` 课堂建议：只要一个表达式里混用了两类以上运算符，就主动加括号，别赌记忆。 --- ## 四、位串上的运算：逐位独立进行 例如： ``` a = 00101101 b = 00010111 ``` 逐位计算： ``` a & b = 00000101 a | b = 00111111 a ^ b = 00111010 ~a = 11010010 ``` 注意：`~a` 的结果长度和机器位数有关。课堂里我们常固定成 8 位或 32 位来讨论。 ### 竖式写法示范（像小学列竖式） 把高位写在左边、低位写在右边，同一列对齐后逐列运算。 1) 按位与 `&` ```text 0 0 1 0 1 1 0 1 (a) & 0 0 0 1 0 1 1 1 (b) ---------------------- 0 0 0 0 0 1 0 1 (a & b) ``` 2) 按位或 `|` ```text 0 0 1 0 1 1 0 1 (a) | 0 0 0 1 0 1 1 1 (b) ---------------------- 0 0 1 1 1 1 1 1 (a | b) ``` 3) 按位异或 `^` ```text 0 0 1 0 1 1 0 1 (a) ^ 0 0 0 1 0 1 1 1 (b) ---------------------- 0 0 1 1 1 0 1 0 (a ^ b) ``` 4) 左移与右移也可按“横向挪位”理解 ```text a : 0 0 1 0 1 1 0 1 a << 2 : 1 0 1 1 0 1 0 0 (左移两格，右侧补 0) a >> 3 : 0 0 0 0 0 1 0 1 (右移三格，左侧补 0) ``` --- ## 五、二进制加法与减法 ### 1. 二进制加法 和十进制竖式一样，也是“本位求和 + 进位”。 单个位相加规则： - $0+0=0$，进位 0 - $0+1=1$，进位 0 - $1+0=1$，进位 0 - $1+1=0$，进位 1 如果再加上原来的进位，就变成三数相加。 竖式例子（8 位）：`00101101 + 00010111` ```text 进位: 0 0 1 1 1 1 1 0 0 1 0 1 1 0 1 + 0 0 0 1 0 1 1 1 ---------------------- 0 1 0 0 0 1 0 0 ``` 可让学生从最右列开始，逐列写“本列结果位”和“向左进位”。 ### 2. 二进制减法 可以按“借位法”逐位减，也可以用补码思想把减法变加法。 在本章练习里，统一按 **32 位无符号整数** 处理： - 超过 $2^{32}-1$ 的高位进位丢弃 - 不足 0 时按 32 位环绕（相当于加上 $2^{32}$） 竖式例子（8 位）：`00101101 - 00010111` ```text 借位: 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 - 0 0 0 1 0 1 1 1 ---------------------- 0 0 0 1 0 1 1 0 ``` 从最右列开始，若不够减就向左借 1（借 1 相当于当前位加 2）。 --- ## 六、C++：用数组模拟按位运算与加减 下面给一份课堂版代码： ```cpp #include using namespace std; const int LEN = 32; // 把无符号整数转成二进制数组：bits[0] 是最低位 void toBits(unsigned int x, int bits[]) { for (int i = 0; i < LEN; i++) { bits[i] = x % 2; x /= 2; } } // 把二进制数组转回无符号整数 unsigned int toUInt(const int bits[]) { unsigned int x = 0; for (int i = LEN - 1; i >= 0; i--) { x = x * 2 + bits[i]; } return x; } // 打印 32 位二进制串（高位在前） void printBits(const int bits[]) { for (int i = LEN - 1; i >= 0; i--) { cout << bits[i]; } cout << '\n'; } void bitAnd(const int a[], const int b[], int c[]) { for (int i = 0; i < LEN; i++) c[i] = a[i] & b[i]; } void bitOr(const int a[], const int b[], int c[]) { for (int i = 0; i < LEN; i++) c[i] = a[i] | b[i]; } void bitXor(const int a[], const int b[], int c[]) { for (int i = 0; i < LEN; i++) c[i] = a[i] ^ b[i]; } void bitNot(const int a[], int c[]) { for (int i = 0; i < LEN; i++) c[i] = 1 - a[i]; } // 32 位无符号加法：溢出进位自动丢弃 void addBits(const int a[], const int b[], int c[]) { int carry = 0; for (int i = 0; i < LEN; i++) { int sum = a[i] + b[i] + carry; c[i] = sum % 2; carry = sum / 2; } } // 32 位无符号减法：逐位借位 void subBits(const int a[], const int b[], int c[]) { int borrow = 0; for (int i = 0; i < LEN; i++) { int cur = a[i] - b[i] - borrow; if (cur >= 0) { c[i] = cur; borrow = 0; } else { c[i] = cur + 2; borrow = 1; } } } int main() { unsigned int A, B; cin >> A >> B; int a[LEN], b[LEN], c[LEN]; toBits(A, a); toBits(B, b); cout << "A = "; printBits(a); cout << "B = "; printBits(b); bitAnd(a, b, c); cout << "A AND B= "; printBits(c); bitOr(a, b, c); cout << "A OR B= "; printBits(c); bitXor(a, b, c); cout << "A XOR B= "; printBits(c); bitNot(a, c); cout << "NOT A = "; printBits(c); addBits(a, b, c); cout << "A + B = " << toUInt(c) << '\n'; subBits(a, b, c); cout << "A - B = " << toUInt(c) << '\n'; return 0; } ``` --- ## 七、练习题 ### 【第一组】按位运算热身（进阶版，8 位） 已知： - `a = 00101101` - `b = 00010111` 1. 求 `a & b`。 2. 求 `a | b`。 3. 求 `a ^ b`。 4. 求 `~a`。 5. 求 `~b`。 6. 求 `(a & b) ^ a`。 7. 求 `(a | b) ^ b`。 8. 求 `(a ^ b) & a`。 9. 求 `(a ^ b) | b`。 10. 求 `(~a) & b`。 11. 求 `(~b) | a`。 12. 求 `a & (~b)`。 13. 求 `(a | b) & (a ^ b)`。 再设： - `c = 01011000` - `d = 00110101` 14. 求 `c & d`。 15. 求 `c | d`。 16. 求 `c ^ d`。 17. 求 `(c ^ d) ^ c`。 18. 求 `(c & d) | (c ^ d)`。 19. 求 `~(c ^ d)`。 20. 求 `(~c) ^ d`。 再做移位： 21. 求 `a << 1`（8 位）。 22. 求 `a << 3`（8 位）。 23. 求 `a >> 2`（8 位）。 24. 求 `b >> 1`（8 位）。 25. 求 `(a << 2) & 0b11111111`（8 位掩码保留）。 26. 求 `(b << 1) ^ (a >> 2)`（8 位）。 --- ### 【第二组】真值与规律（先判断，再写一句理由） 27. 对任意位串 `x`，是否总有 `x ^ x == 0`？ 28. 对任意位串 `x`，是否总有 `x & x == x`？ 29. 对任意位串 `x`，是否总有 `x | x == x`？ 30. 对任意位串 `x`，是否总有 `x ^ 0 == x`？ 31. 对任意位串 `x`，是否总有 `x ^ FULL_MASK == ~x`？（其中 `FULL_MASK` 指整个位宽全 1） 32. 对任意位串 `x`，是否总有 `(~x) & x == 0`？ 33. 对任意位串 `x`，是否总有 `(~x) | x == FULL_MASK`？ 34. 对任意非负整数 `x`，是否总有 `(x << 1) == 2 * x`？ 35. 对任意非负整数 `x`，是否总有 `(x >> 1) == x / 2`（整除）？ 36. 若 `x` 是 2 的幂，是否总有 `x > 0 && (x & (x - 1)) == 0`？ --- ### 【第三组】加减法进阶（8 位，丢弃溢出位） 37. 计算：`00000101 + 00000110` 38. 计算：`11111111 + 00000001` 39. 计算：`00001010 - 00000011` 40. 计算：`00000000 - 00000001` 41. 计算：`10000000 + 10000000` 42. 计算：`01111111 + 00000001` 43. 计算：`01010101 + 00110011` 44. 计算：`00100000 - 00011111` 45. 计算：`00010000 - 00100000` 46. 计算：`10101010 - 01010101` --- ### 【第四组】逆向构造题（更像算法题） 设 `a = 11001010`，求一个 8 位 `x`，使得： 47. `a & x == 10001000`（若有多解，写出任意一个） 48. `a | x == 11101110`（若有多解，写出任意一个） 49. `a ^ x == 01100111`（写唯一解） 再设 `u = 00110110`，`v = 00000110`： 50. 构造一个 8 位 `y`，使得 `y & u == v`。 51. 判断是否存在 8 位 `z`，使得 `z | u == v`，若存在给出一个，若不存在说明原因。 --- ### 【第五组】常用位技巧（探究题，重点） 这一组不要先背公式，先按题目把例子算出来，再归纳。 #### A. 探究“最低位 1”（lowbit） 对下面每个 `x`，先写出二进制，再计算 `-x`（按补码），最后算出 `x & (-x)`： 52. `x = 12` 53. `x = 40` 54. `x = 44` 55. `x = 72` 56. 观察 52-55 的结果，归纳一句话：`x & (-x)` 保留了 `x` 的哪一部分？ #### B. 探究“去掉最低位 1” 对下面每个 `x`，计算 `x - 1`，再算 `x & (x - 1)`： 57. `x = 12` 58. `x = 40` 59. `x = 44` 60. `x = 72` 61. 观察 57-60 的结果，归纳一句话：`x & (x-1)` 对二进制位做了什么变化？ #### C. 由例子得到“2 的幂”判定 分别计算 `x & (x - 1)`，并记录是否为 0： 62. `x = 1` 63. `x = 2` 64. `x = 4` 65. `x = 8` 66. `x = 3` 67. `x = 6` 68. 根据 62-67，总结：当 `x > 0` 时，什么条件等价于“`x` 是 2 的幂”？ #### D. 应用题（把结论用起来） 69. 不用循环，判断 `64` 是否是 2 的幂，并写出关键表达式值。 70. 不用循环，判断 `72` 是否是 2 的幂，并写出关键表达式值。 71. 设 `x = 01011000`（8 位），先求 `x & (-x)`，再给出最低位 1 的位置（最低位记第 0 位）。 72. 设 `x = 00101000`（8 位），先求 `x & (-x)`，再给出最低位 1 的位置（最低位记第 0 位）。 73. 设 `x = 10000000`（8 位），先求 `x & (-x)`，再给出最低位 1 的位置（最低位记第 0 位）。 74. 从 `x = 90` 开始，反复执行 `x = x & (x - 1)` 直到变成 0，需要几步？由此得到 `90` 的二进制中有几个 1？ 75. 给定偶数 `n`，写出一个表达式快速判断它是否能被 4 整除，并说明对应的“二进制末尾特征”。 ## 参考答案 **第一组** 1. `00000101` 2. `00111111` 3. `00111010` 4. `11010010` 5. `11101000` 6. `00101000` 7. `00101000` 8. `00101000` 9. `00111111` 10. `00010010` 11. `11101101` 12. `00101000` 13. `00111010` 14. `00010000` 15. `01111101` 16. `01101101` 17. `00110101` 18. `01111101` 19. `10010010` 20. `10010010` 21. `01011010` 22. `01101000` 23. `00001011` 24. `00001011` 25. `10110100` 26. `00100101` **第二组** 27. 是。 28. 是。 29. 是。 30. 是。 31. 是（全 1 掩码下逐位翻转）。 32. 是。 33. 是。 34. 在不溢出的前提下是。 35. 是（无符号或非负整数语境下）。 36. 是。 **第三组** 37. `00001011`（十进制 11） 38. `00000000`（十进制 0） 39. `00000111`（十进制 7） 40. `11111111`（十进制 255） 41. `00000000`（十进制 0） 42. `10000000`（十进制 128） 43. `10001000`（十进制 136） 44. `00000001`（十进制 1） 45. `11110000`（十进制 240） 46. `01010101`（十进制 85） **第四组（给一种可行解）** 47. 可取 `x = 10001100`。 48. 可取 `x = 01100100`。 49. 唯一解 `x = 10101101`。 50. 可取 `y = 11100110`（只要在 `u` 为 1 的位上与 `v` 对齐即可，`u` 为 0 的位任意）。 51. 不存在，因为按位或不会把 `u` 中的 1 变成 0，而 `u = 00110110` 在第 5、4、2、1 位已有 1，但 `v = 00000110` 在第 5、4 位是 0。 **第五组** 52. `12 = 1100`，`-12`（8 位）是 `11110100`，`12 & (-12) = 0100`（十进制 4） 53. `40 = 101000`，`40 & (-40) = 001000`（十进制 8） 54. `44 = 101100`，`44 & (-44) = 000100`（十进制 4） 55. `72 = 1001000`，`72 & (-72) = 0001000`（十进制 8） 56. 结论：`x & (-x)` 只保留最低位的 1，其余位清零（即 lowbit） 57. `12 & 11 = 1100 & 1011 = 1000`（十进制 8） 58. `40 & 39 = 101000 & 100111 = 100000`（十进制 32） 59. `44 & 43 = 101100 & 101011 = 101000`（十进制 40） 60. `72 & 71 = 1001000 & 1000111 = 1000000`（十进制 64） 61. 结论：`x & (x-1)` 会把最低位 1 消掉，且更低位保持为 0 62. `1 & 0 = 0` 63. `2 & 1 = 0` 64. `4 & 3 = 0` 65. `8 & 7 = 0` 66. `3 & 2 = 2`（非 0） 67. `6 & 5 = 4`（非 0） 68. 结论：`x > 0 && (x & (x - 1)) == 0` 当且仅当 `x` 是 2 的幂 69. `64 & 63 = 0`，所以是 2 的幂 70. `72 & 71 = 64`，非 0，所以不是 2 的幂 71. lowbit 是 `00001000`（8），最低位 1 在第 3 位 72. lowbit 是 `00001000`（8），最低位 1 在第 3 位 73. lowbit 是 `10000000`（128），最低位 1 在第 7 位 74. `90 -> 88 -> 80 -> 64 -> 0`，共 4 步，所以有 4 个 1 75. 可用 `(n & 3) == 0`，对应二进制末两位为 `00`