596 lines
15 KiB
Markdown
596 lines
15 KiB
Markdown
# 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 <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`
|