第22章 位运算

22.1 位运算的基本概念

位运算的操作对象是整数的二进制表示，包括 signed（有符号）和 unsigned（无符号）。运算时忽略符号的"含义"，仅对每一位做逻辑/算术操作。

例如整数 5（二进制 00000101）和 3（00000011），位运算直接对每一位操作。

22.2 常用的位运算符

22.2.1 按位与（&）

两个对应位都为 1 时结果位为 1，否则为 0。 $0 \& 0=0;\ 0 \& 1=0;\ 1 \& 0=0;\ 1 \& 1=1$ 示例：$5(00000101) \& 3(00000011) = 1(00000001)$

应用：清零（a & 0）；截取指定位（a & 0x0F 取低 4 位）；判断奇偶（a & 1）。

22.2.2 按位或（|）

两个对应位至少有一个为 1 时结果位为 1。 $0 | 0=0;\ 0 | 1=1;\ 1 | 0=1;\ 1 | 1=1$ 示例：$5(00000101) | 3(00000011) = 7(00000111)$

应用：置位（把某位设为 1），如 a | (1 << 3) 把第 3 位置 1。

22.2.3 按位异或（^）

两位不同则为 1，相同则为 0。 $0 \oplus 0=0;\ 0 \oplus 1=1;\ 1 \oplus 0=1;\ 1 \oplus 1=0$ 示例：$5(00000101) \oplus 3(00000011) = 6(00000110)$

应用：翻转掩码对应位（a ^ 0x0F 翻转低 4 位）；不借助临时变量交换两数。

22.2.4 按位取反（~）

所有位 0 变 1、1 变 0。示例：~5 在 32 位系统结果为 0xFFFFFFFA，满足公式 ~a = -a - 1。

22.2.5 左移（<<）

二进制整体左移 N 位，高位丢弃，低位补 0。 示例：$5(00000101) << 2 = 20(00010100)$ 特性：无符号/正数左移 N 位 ≈ 乘 $2^N$（不溢出时）。

22.2.6 右移（>>）

• 无符号 unsigned：逻辑右移，低位丢弃，高位补 0；
• 有符号 signed：算术右移，低位丢弃，高位补符号位（正补 0，负补 1）。 示例：无符号 $8 >> 2 = 2$；8 位有符号 $-8(11111000) >> 2 = -2(11111110)$ 特性：正数/无符号右移 N 位 ≈ 除 $2^N$（向下取整）。

22.3 异或交换变量

#include <iostream>
using namespace std;
int main() {
    int a = 5, b = 10;
    cout << "交换前：a=" << a << ", b=" << b << endl;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    cout << "交换后：a=" << a << ", b=" << b << endl;
    return 0;
}

22.4 位运算符优先级（从高到低）

~ > << >> > & > ^ > |

复杂表达式建议加括号，避免歧义。

#include <iostream>
using namespace std;
int main() {
    int a = 5, b = 3;
    int c = a & b | 1;   // 先算 & ：5&3=1，再 1|1=1
    int d = a & (b | 1); // 先算 | ：3|1=3，再 5&3=1
    cout << "c=" << c << " d=" << d << endl;  // c=1 d=1
    return 0;
}

22.5 位运算应用场景

1. 嵌入式硬件寄存器位控制；
2. 图像 RGB 通道提取；
3. 高效判断奇偶：(a & 1) == 1；
4. 快速生成 2 的幂：1 << n；
5. 加密、压缩的底层二进制处理；
6. 状态压缩：用一个整数的不同 bit 表示多个布尔开关。

22.6 综合示例：用位运算实现常见技巧

#include <iostream>
using namespace std;

int main() {
    int x = 12; // 二进制 1100

    // 1) 判断奇偶
    cout << x << (x & 1 ? " 是奇数" : " 是偶数") << endl;

    // 2) 取第 k 位（k 从 0 开始）
    int k = 2;
    cout << "第 " << k << " 位 = " << ((x >> k) & 1) << endl; // 1100 第2位是 1

    // 3) 把第 k 位置 1 / 置 0
    cout << "第1位置1: " << (x | (1 << 1)) << endl;   // 1110 = 14
    cout << "第2位置0: " << (x & ~(1 << 2)) << endl;  // 1000 = 8

    // 4) 快速乘/除 2 的幂
    cout << "12 << 1 = " << (x << 1) << " (相当于 x*2)" << endl;
    cout << "12 >> 2 = " << (x >> 2) << " (相当于 x/4)" << endl;
    return 0;
}

22.7 使用注意事项

1. 有符号数右移会补符号位，逻辑操作优先用 unsigned；
2. 左移位数 ≥ 类型位宽时结果未定义（如 1 << 31 对 32 位 int 是未定义行为）；
3. 位运算可读性差，必须加注释；
4. 32/64 位系统 int 长度不同，跨平台注意位数差异。

22.8 选择题练习

1. 表达式 5 & 3 的值是？（5=0101，3=0011）

A. 1
B. 7
C. 6
D. 0

2. 表达式 5 | 3 的值是？

A. 1
B. 7
C. 6
D. 15

3. 表达式 5 ^ 3 的值是？

A. 1
B. 7
C. 6
D. 2

4. 在 C++ 中，1 << 3 等价于？

A. 3
B. 6
C. 8
D. 9

5. 无符号整数 16 >> 2 的结果是？

A. 4
B. 8
C. 2
D. 1

6. 判断一个整数 n 是否为奇数，最简洁的写法是？

A. n % 2 == 1
B. (n & 1) == 1
C. n / 2 != 0
D. n >> 1 == 0