C: 位运算
位运算就像控制一排灯的开关——每盏灯对应一个比特，你可以单独开、关、翻转某一盏，而不影响其他灯。
1. 二进制回顾
计算机内部用二进制表示所有数据。一个字节（byte）= 8 个比特（bit），每个比特是 0 或 1。
C
十进制 42 = 二进制 00101010
十进制 255 = 二进制 11111111
有符号整数用补码表示：最高位是符号位，0 为正，1 为负。
C
十进制 5 = 00000101
十进制 -5 = 11111011 (补码)
2. 六种位运算符
| 运算符 | 名称 | 规则 |
|---|---|---|
& |
按位与 | 两位都为1结果才为1 |
| |
按位或 | 有一位为1结果就为1 |
^ |
按位异或 | 两位不同结果为1 |
~ |
按位取反 | 0变1，1变0 |
<< |
左移 | 各位左移，低位补0 |
>> |
右移 | 各位右移，高位补符号位(有符号)或0(无符号) |
(1) 按位与 (&)
C
1010 (10)
& 1100 (12)
------
1000 (8)
用途：清除某些位、检查某些位是否为1。
(2) 按位或 (|)
C
1010 (10)
| 1100 (12)
------
1110 (14)
用途：设置某些位为1。
(3) 按位异或 (^)
C
1010 (10)
^ 1100 (12)
------
0110 (6)
特性：a ^ a = 0，a ^ 0 = a。异或是可逆的，用同一个值异或两次就还原了。
(4) 按位取反 (~)
C
~ 00101010 (42)
= 11010101 (-43, 补码)
对无符号数：~0 = 255(8位)，~0 = 0xFFFFFFFF(32位)。
(5) 左移 (<<)
C
5 << 2
= 00000101 << 2
= 00010100
= 20
左移 n 位等于乘以 2^n。5 << 2 = 5 * 4 = 20。
(6) 右移 (>>)
C
20 >> 2
= 00010100 >> 2
= 00000101
= 5
右移 n 位等于除以 2^n（向下取整）。
⚠️ 对有符号负数右移，高位补1（算术右移），结果可能不符合预期。建议只对无符号数做移位。
3. 位操作四大操作
(1) 设置位（置1）
C
flags |= (1 << n);
把第 n 位设为 1，其他位不变。
(2) 清除位（置0）
C
flags &= ~(1 << n);
~(1 << n) 产生一个除第 n 位为 0 外全为 1 的掩码，与运算后第 n 位清零。
(3) 翻转位
C
flags ^= (1 << n);
异或运算：0^1=1，1^1=0，正好实现翻转。
(4) 检查位
C
if (flags & (1 << n)) {
}
如果第 n 位是 1，结果非零；是 0 则结果为零。
▶ 示例
C
#include <stdio.h>
void print_bits(unsigned char val) {
for (int i = 7; i >= 0; i--) {
printf("%d", (val >> i) & 1);
}
printf("\n");
}
int main(void) {
unsigned char flags = 0;
flags |= (1 << 3);
printf("设置第3位: ");
print_bits(flags);
flags |= (1 << 5);
printf("设置第5位: ");
print_bits(flags);
flags &= ~(1 << 3);
printf("清除第3位: ");
print_bits(flags);
flags ^= (1 << 5);
printf("翻转第5位: ");
print_bits(flags);
flags ^= (1 << 7);
printf("翻转第7位: ");
print_bits(flags);
if (flags & (1 << 7)) {
printf("第7位是1\n");
}
return 0;
}
TEXT
📖 仅展示
设置第3位: 00001000
设置第5位: 00101000
清除第3位: 00100000
翻转第5位: 00000000
翻转第7位: 10000000
第7位是1
4. 掩码技术
掩码（mask）是一组预定义的位组合，用来提取或修改数据中的特定位域。
(1) 提取低位
C
unsigned int val = 0xABCD;
unsigned int low_byte = val & 0xFF;
0xFF 是掩码，只保留最低 8 位。
(2) 提取高位
C
unsigned int high_byte = (val >> 8) & 0xFF;
先右移 8 位，再用掩码取低 8 位。
(3) 组合值
C
unsigned int combined = (high << 8) | low;
把两个字节拼成一个 16 位值。
▶ 示例
RGB 颜色值提取。一个 24 位颜色值，红绿蓝各占 8 位：
C
#include <stdio.h>
int main(void) {
unsigned int color = 0xFF6633;
unsigned char r = (color >> 16) & 0xFF;
unsigned char g = (color >> 8) & 0xFF;
unsigned char b = color & 0xFF;
printf("颜色 #FF6633:\n");
printf(" 红: %d\n", r);
printf(" 绿: %d\n", g);
printf(" 蓝: %d\n", b);
unsigned int new_color = 0x00;
new_color |= ((r / 2) << 16);
new_color |= ((g / 2) << 8);
new_color |= (b / 2);
printf("变暗后: #%06X\n", new_color);
return 0;
}
TEXT
📖 仅展示
颜色 #FF6633:
红: 255
绿: 102
蓝: 51
变暗后: #7F3319
🔥 RGB 颜色提取就是位运算的经典应用。网页开发中 #RRGGBB 格式本质上就是 24 位整数，红在 16-23 位，绿在 8-15 位，蓝在 0-7 位。
5. 权限标志位
Linux 文件权限是位运算的典型应用。9 位权限分别表示 owner/group/other 的 read/write/execute：
C
rwxr-xr-x = 111101101 = 0755
rw-r--r-- = 110100100 = 0644
C
#include <stdio.h>
#define READ (1 << 2)
#define WRITE (1 << 1)
#define EXECUTE (1 << 0)
void show_permission(unsigned char perm) {
printf("%c", (perm & READ) ? 'r' : '-');
printf("%c", (perm & WRITE) ? 'w' : '-');
printf("%c", (perm & EXECUTE) ? 'x' : '-');
}
int main(void) {
unsigned char owner = READ | WRITE | EXECUTE;
unsigned char group = READ | EXECUTE;
unsigned char other = READ | EXECUTE;
printf("权限: ");
show_permission(owner);
show_permission(group);
show_permission(other);
printf("\n");
owner &= ~WRITE;
printf("去掉写权限后: ");
show_permission(owner);
show_permission(group);
show_permission(other);
printf("\n");
return 0;
}
TEXT
📖 仅展示
权限: rwxr-xr-x
去掉写权限后: r-xr-xr-x
TEXT
📖 仅展示
权限: rwxr-xr-x
去掉写权限后: r-xr-xr-x
6. 位运算实用技巧
(1) 交换两个变量（不用临时变量）
C
a ^= b;
b ^= a;
a ^= b;
原理：异或的自反性。但可读性差，实际开发中不推荐使用。
(2) 判断奇偶
C
if (n & 1) {
}
最低位为 1 就是奇数。比 n % 2 更快。
(3) 乘除 2 的幂
C
n << 1
n << 2
n >> 1
编译器通常会把 n * 2 优化成移位，但移位只对正整数安全。
(4) 计算 2 的幂次
C
unsigned int pow2 = 1u << n;
1u << 0 = 1，1u << 1 = 2，1u << 8 = 256……用移位比 pow(2, n) 快得多。
(5) 对齐到 2 的幂
C
unsigned int aligned = (value + mask) & ~mask;
比如对齐到 4 字节边界：(n + 3) & ~3。
C
#include <stdio.h>
int main(void) {
int values[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 0; i < 10; i++) {
int aligned = (values[i] + 3) & ~3;
printf("%d -> %d\n", values[i], aligned);
}
return 0;
}
TEXT
📖 仅展示
0 -> 0
1 -> 4
2 -> 4
3 -> 4
4 -> 4
5 -> 8
6 -> 8
7 -> 8
8 -> 8
9 -> 12
❓ 常见问题
Q 为什么移位运算比乘除法快？
A 移位是 CPU 单周期指令，乘除法需要多个时钟周期。但现代编译器会自动把乘以2的幂优化成移位，不必手动写。
Q 位运算能用于浮点数吗？
A 不能。位运算符只适用于整数类型。要操作浮点数的位，需要通过
memcpy 把浮点数的字节复制到整数中。Q 异或交换变量有什么问题？
A 如果 a 和 b 指向同一块内存（比如是同一个变量的引用），异或交换会让值变成 0。而且可读性差，编译器优化后普通交换效率一样高。
📖 小节
- 六种位运算符：
&、|、^、~、<<、>> - 设置位用
|=，清除位用&= ~，翻转位用^=，检查位用& - 掩码是位运算的核心技术，用于提取和组合位域
- 权限标志位用或运算组合，与运算检查，取反清除
- 左移乘 2，右移除 2，对齐用
(n + mask) & ~mask
📝 作业
- 编写函数，返回一个整数的二进制中 1 的个数（用位运算实现，不用循环除2）
- 编写程序，用位运算实现 RGB 颜色的亮度调整（每个通道乘以一个系数后重新组合）
- 编写函数，将一个 32 位整数的第 m 位到第 n 位提取出来（m < n，从0开始计数）
