hustoj/web/doc/3.2 二进制运算.md

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. 按位与 &

    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. 按位或 |

    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. 按位异或 ^

    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. 左移与右移也可按“横向挪位”理解

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

进位: 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

借位:  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++：用数组模拟按位运算与加减

下面给一份课堂版代码：

#include <bits/stdc++.h>
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