第 86 课 - 位运算基础

学习目标

完成本课学习后，你将能够：

理解计算机中数据的二进制表示基础。
掌握与(&)、或(|)、异或(^)、取反(~)四种基本位逻辑运算。
掌握左移(<<)和右移(>>)操作的原理与用途。
学会使用掩码(Mask)进行位的提取与设置。

核心概念

1. 二进制：计算机的“母语”

计算机的一切数据（数字、字符、图片）最终都以二进制（由 0 和 1 组成的序列）的形式存储在内存中。一个二进制位（bit）是信息的最小单位，值为 0 或 1。

例如，十进制数 5 的二进制表示是 101。为了方便计算，我们通常用固定长度来表示（如8位：00000101）。
位运算，顾名思义，就是直接对数据的二进制位进行操作，它是计算机最底层、最高效的运算方式。

2. 位逻辑运算符

这些运算符对两个操作数的对应位进行逻辑判断。

与 & (AND): 两位都为1，结果才为1。类似于“并且”的关系。

1010 (10)
& 1100 (12)
------
1000 (8) // 只有第三位都是1

或 | (OR): 两位中只要有一个为1，结果就为1。类似于“或者”的关系。

1010 (10)
| 1100 (12)
------
1110 (14) // 只要有1，结果就是1

异或 ^ (XOR): 两位不同则为1，相同则为0。可以理解为“找不同”。

1010 (10)
^ 1100 (12)
------
0110 (6) // 第二位和第三位不同

取反 ~ (NOT): 单目运算符，将每一位取反（0变1，1变0）。注意：在计算机中，负数通常用补码表示，所以 ~ 的结果往往是 -(x+1)。

对于8位有符号整数，~5 (00000101) 的结果是 11111010，它代表 -6（补码）。

3. 移位运算符

移位操作可以快速地实现乘以或除以 2 的幂。

左移 <<: 将二进制位向左移动指定位数，右边用 0 填充。左移 n 位相当于乘以 2^n。

00000101 (5) << 1
= 00001010 (10) // 5 * 2 = 10

右移 >>: 将二进制位向右移动指定位数。
对于无符号数或正数，左边用 0 填充（逻辑右移）。右移 n 位相当于除以 2^n 并向下取整。
对于有符号负数，左边通常用符号位（1）填充（算术右移），以保持符号。

00001010 (10) >> 1
= 00000101 (5) // 10 // 2 = 5

4. 掩码 (Mask)

掩码是一个用于“选择”或“操作”指定位的二进制数。通常将想操作的位设为1，不关心的位设为0。

提取某一位: 使用 & 和掩码。 x & (1 << n) 可以检查 x 的第 n 位（从0开始计数）是否为1。
设置某一位为1: 使用 | 和掩码。 x | (1 << n) 会将 x 的第 n 位设为1，其他位不变。
清零某一位: 使用 & 和掩码的反码。 x & ~(1 << n) 会将 x 的第 n 位清零，其他位不变。

代码示例

以下 Python 代码演示了基本的位运算操作。Python 用 bin() 函数可以方便地查看二进制表示。

# 定义两个用于演示的整数
a = 10  # 二进制: 0b1010 (或 1010)
b = 12  # 二进制: 0b1100 (或 1100)

print(f"a = {a}, 二进制: {bin(a)}")
print(f"b = {b}, 二进制: {bin(b)}")
print("-" * 30)

# 1. 基本位逻辑运算
and_result = a & b
print(f"a & b = {and_result}, 二进制: {bin(and_result)}")  # 结果: 8 (0b1000)

or_result = a | b
print(f"a | b = {or_result}, 二进制: {bin(or_result)}")   # 结果: 14 (0b1110)

xor_result = a ^ b
print(f"a ^ b = {xor_result}, 二进制: {bin(xor_result)}") # 结果: 6 (0b0110)

not_result = ~a
print(f"~a = {not_result}, 二进制 (补码): {bin(not_result & 0xFF)}")  # 与0xFF是为了看8位表示，结果: 245 (0b11110101)，在数学上是 -11
print("-" * 30)

# 2. 移位运算
shift_left = a << 1  # 左移1位，相当于乘以2
print(f"a << 1 = {shift_left}, 二进制: {bin(shift_left)}")  # 结果: 20 (0b10100)

shift_right = b >> 2  # 右移2位，相当于除以4
print(f"b >> 2 = {shift_right}, 二进制: {bin(shift_right)}") # 结果: 3 (0b11)
print("-" * 30)

# 3. 掩码应用示例
x = 0b10110100  # 180
n = 3           # 我们想操作从右往左数第3位（从0开始）

# 检查第n位是否为1
is_set = (x >> n) & 1  # 或者使用 x & (1 << n)
print(f"检查 180 (0b{bin(x)[2:]}) 的第 {n} 位: {is_set}")  # 结果: 1 (为真)

# 将第n位设为1
set_bit = x | (1 << n)
print(f"将第 {n} 位设为1后: {set_bit}, 二进制: {bin(set_bit)}") # 结果: 184 (0b10111100)

# 将第n位清零
clear_bit = x & ~(1 << n)
print(f"将第 {n} 位清零后: {clear_bit}, 二进制: {bin(clear_bit)}") # 结果: 176 (0b10110000)

# 切换第n位 (Toggle)
toggle_bit = x ^ (1 << n)
print(f"切换第 {n} 位后: {toggle_bit}, 二进制: {bin(toggle_bit)}") # 结果: 180 ^ 8 = 188 (0b10111100)

实践练习

练习 1：判断奇偶

要求：编写一个函数 is_odd(n)，利用位运算判断一个整数 n 是否为奇数。提示：奇数的二进制表示最后一位一定是1。 预期输出：

is_odd(5) -> True
is_odd(4) -> False
is_odd(-3) -> True

练习 2：提取第k位

要求：编写一个函数 get_bit(num, k)，返回整数 num 的二进制表示中从右往左数的第 k 位（k从0开始）的值。 预期输出：

get_bit(10, 1) -> 1  # 10的二进制是1010，第1位是1
get_bit(10, 2) -> 0  # 第2位是0

练习 3：不用临时变量交换两个数

要求：仅使用位运算（异或 ^），交换两个整数变量 a 和 b 的值。提示：异或的性质：x ^ x = 0，x ^ 0 = x。 预期输出：

交换前: a=5, b=7
交换后: a=7, b=5

常见错误

混淆逻辑运算和位运算：初学者容易将 & 与 and，| 与 or 混淆。and/or 是逻辑运算，操作的是整个布尔值（True/False），结果是布尔值。而 &/| 是位运算，操作的是数字的二进制位。
```
a = 1
b = 2
# 逻辑运算，将非零值视为True
print(a and b) # 输出 2 (因为True and 2 返回 2)
# 位运算，直接对二进制位操作
print(a & b)   # 输出 0 (001 & 010 = 000)
```
移位时的溢出与符号问题：
- 在像 C/C++/Java 这样的语言中，左移一个超出类型范围的位数是未定义行为。右移有符号负数的行为（算术右移还是逻辑右移）也可能依赖于具体实现。在 Python 中，整数是任意精度的，所以左移不会溢出，右移行为是统一的（算术右移）。
运算符优先级：位运算符的优先级通常低于比较运算符和算术运算符，但高于逻辑运算符。为了避免错误，建议在复杂表达式中使用括号。
```
# 错误写法：意图是先移位再加法
result = x << 2 + 1   # 实际是 x << (2 + 1)，即 x << 3
# 正确写法：
result = (x << 2) + 1
```

小结

位运算的本质：直接操作数据的二进制位，是计算机最底层、最高效的操作之一。
四大逻辑运算：&（与）、|（或）、^（异或）、~（取反），是构建位操作技巧的基石。
移位运算：<<（左移，等效于乘以2的幂）、>>（右移，等效于除以2的幂），能实现快速的乘除。
掩码的力量：通过设计特定的二进制掩码（1 << n），结合 &、|、^ 运算符，可以精确地检查、设置、清除或切换一个整数中任意特定位。
效率优势：位运算通常只需要一个 CPU 指令周期，比乘除法等高级运算快得多，在对性能要求极高的场景（如嵌入式系统、图形学、密码学）中至关重要。

掌握位运算基础，是理解计算机底层原理和提升算法性能的重要一步。在接下来的课程中，我们将学习更多基于这些基础操作的实用技巧。

练习编辑器

rust