1. 为什么需要位运算？

我第一次接触位运算是在大学的数据结构课上，当时教授用位运算实现了一个超快的素数筛法，比传统方法快了近10倍。这让我意识到，在底层编程中，位运算就像一把瑞士军刀，能解决许多看似复杂的问题。

你可能不知道，你每天使用的手机、电脑，甚至是智能手表，底层都在大量使用位运算。比如：

• 嵌入式设备通过位操作控制硬件寄存器
• 游戏引擎用位掩码管理物体碰撞层级
• 数据库系统用位图加速查询
• 压缩算法用位移操作处理数据

位运算之所以高效，是因为它直接操作二进制位，跳过了高级语言的抽象层。在C/C++中，一个简单的位操作通常对应一条CPU指令，而同样的功能如果用算术运算实现，可能需要多条指令。

2. 二进制基础回顾

2.1 二进制表示

在计算机中，所有数据最终都以二进制形式存储。一个二进制位（bit）有0和1两种状态，8个bit组成一个字节（byte）。例如：

unsigned char a = 42; // 二进制: 00101010

C/C++中常用的整型类型及其表示范围：

2.2 原码、反码和补码

理解负数表示对位运算至关重要：

1. 原码：最高位表示符号，0为正，1为负

   • +5: 00000101
   • -5: 10000101

2. 反码：正数同原码，负数符号位不变，其余取反

   • -5: 11111010

3. 补码（现代计算机通用）：正数同原码，负数为反码+1

   • -5: 11111011

补码的优势是加减法可以统一处理，不需要特殊考虑符号位。

3. 位运算符详解

3.1 按位与(&)

运算规则：两位都为1时结果为1，否则为0

0 & 0 = 0 0 & 1 = 0 1 & 0 = 0 1 & 1 = 1

实用技巧：

1. 清零特定位：a & ~(1 << n)
2. 取指定位：a & (1 << n)
3. 判断奇偶：if(a & 1)比if(a % 2)更快

// 示例：检查第3位是否为1 uint8_t a = 0b10101010; if(a & (1 << 3)) { printf("第3位是1\n"); }

3.2 按位或(|)

运算规则：两位有1则1，全0才0

0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1

实用技巧：

1. 设置特定位：a | (1 << n)
2. 合并标志位

// 设置第2位为1 uint8_t a = 0b10101010; a |= (1 << 2); // 结果: 0b10101110

3.3 按位异或(^)

运算规则：两位不同则1，相同则0

0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0

神奇特性：

1. 交换两个数：a ^= b; b ^= a; a ^= b;
2. 与0异或不变：a ^ 0 = a
3. 自反性：a ^ b ^ b = a

// 交换两个变量(无临时变量) int x = 10, y = 20; x ^= y; y ^= x; x ^= y;

3.4 按位取反(~)

运算规则：0变1，1变0

~0 = 1 ~1 = 0

注意：取反操作会影响所有位，包括符号位

uint8_t a = 0b00001111; uint8_t b = ~a; // 结果: 0b11110000

3.5 位移运算符(<<和>>)

左移(<<)：高位丢弃，低位补0
右移(>>)：低位丢弃，高位补符号位(算术右移)或0(逻辑右移)

实用技巧：

1. 乘以2^n：a << n
2. 除以2^n：a >> n
3. 构造掩码：(1 << n) - 1

// 快速计算2的10次方 int pow2_10 = 1 << 10; // 1024 // 提取低4位 uint8_t low4 = a & 0x0F; // 等价于 uint8_t low4 = a & ((1 << 4) - 1);

4. 位运算实战技巧

4.1 高效状态管理

用单个整型变量存储多个布尔状态：

#define FLAG_A (1 << 0) #define FLAG_B (1 << 1) #define FLAG_C (1 << 2) uint8_t flags = 0; // 设置标志位 flags |= FLAG_A; // 设置A flags |= FLAG_C; // 设置C // 清除标志位 flags &= ~FLAG_B; // 清除B // 检查标志位 if(flags & FLAG_A) { // A标志已设置 } // 切换标志位 flags ^= FLAG_C; // 如果C已设置则清除，未设置则设置

4.2 快速乘除法

虽然现代编译器会自动优化，但在某些场景下手动使用位移仍有益处：

// 快速乘以9 int multiply9(int x) { return (x << 3) + x; // 8x + x = 9x } // 快速除以2 int divide2(int x) { return x >> 1; // 注意负数的处理 }

4.3 位操作实现加减乘除

面试常考题：不用算术运算符实现基本运算

// 加法实现 int add(int a, int b) { while(b != 0) { int carry = a & b; // 计算进位 a = a ^ b; // 非进位加法 b = carry << 1; // 进位左移 } return a; } // 减法实现 int subtract(int a, int b) { return add(a, add(~b, 1)); // a + (-b) }

4.4 位运算在嵌入式中的应用

在寄存器操作中，位运算必不可少：

// 设置GPIO引脚(假设寄存器地址为0x40000000) #define GPIO_BASE 0x40000000 volatile uint32_t *gpio = (uint32_t *)GPIO_BASE; // 设置第5引脚为输出模式 *gpio |= (1 << 5); // 清除第3引脚 *gpio &= ~(1 << 3); // 切换第7引脚状态 *gpio ^= (1 << 7);

5. 高级位操作技巧

5.1 统计1的个数

// 方法1：逐位检查 int countBits1(uint32_t n) { int count = 0; while(n) { count += n & 1; n >>= 1; } return count; } // 方法2：Brian Kernighan算法(更高效) int countBits2(uint32_t n) { int count = 0; while(n) { n &= (n - 1); count++; } return count; }

5.2 判断是否为2的幂

bool isPowerOfTwo(uint32_t n) { return n && !(n & (n - 1)); }

5.3 交换奇偶位

uint32_t swapOddEvenBits(uint32_t x) { return ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1); }

5.4 位反转

uint32_t reverseBits(uint32_t n) { n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1); n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2); n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4); n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8); n = ((n >> 16) | (n << 16)); return n; }

6. 性能优化与注意事项

6.1 位运算与性能

虽然位运算通常很快，但要注意：

1. 现代CPU有流水线，过度优化可能适得其反
2. 某些位运算(如除法替代)可能不如原生指令快
3. 可读性很重要，只在关键路径使用位运算优化

6.2 常见陷阱

1. 位移越界：1 << 32在32位系统是未定义行为
2. 符号位问题：右移有符号数时高位补符号位
3. 运算顺序：位运算符优先级低于算术运算符

// 错误示例 if(x & 1 == 0) // 实际解析为x & (1 == 0) // 正确写法 if((x & 1) == 0)

6.3 跨平台兼容性

不同平台可能存在的问题：

1. 字节序(大端/小端)影响位域解释
2. 有符号数右移行为可能不同
3. 数据类型大小可能不同

建议：

• 使用固定宽度类型(uint32_t等)
• 避免对有符号数进行位运算
• 编写明确的注释

7. 实际工程案例

7.1 位图(Bitmap)实现

位图是位运算的经典应用，用于高效存储和查询大量布尔值：

#define BITS_PER_WORD 32 #define WORD_OFFSET(b) ((b) / BITS_PER_WORD) #define BIT_OFFSET(b) ((b) % BITS_PER_WORD) void setBit(uint32_t *bitmap, int bit) { bitmap[WORD_OFFSET(bit)] |= (1 << BIT_OFFSET(bit)); } void clearBit(uint32_t *bitmap, int bit) { bitmap[WORD_OFFSET(bit)] &= ~(1 << BIT_OFFSET(bit)); } int testBit(uint32_t *bitmap, int bit) { return bitmap[WORD_OFFSET(bit)] & (1 << BIT_OFFSET(bit)); }

7.2 内存池管理

使用位运算高效管理内存块：

#define POOL_SIZE 1024 uint32_t bitmap[POOL_SIZE / 32]; int allocBlock() { for(int i = 0; i < POOL_SIZE/32; i++) { if(bitmap[i] != 0xFFFFFFFF) { // 有空闲块 for(int j = 0; j < 32; j++) { if(!(bitmap[i] & (1 << j))) { bitmap[i] |= (1 << j); return i * 32 + j; } } } } return -1; // 无空闲块 } void freeBlock(int block) { bitmap[WORD_OFFSET(block)] &= ~(1 << BIT_OFFSET(block)); }

7.3 颜色操作

图形处理中常用位运算操作颜色值：

// ARGB颜色操作 #define GET_ALPHA(color) (((color) >> 24) & 0xFF) #define GET_RED(color) (((color) >> 16) & 0xFF) #define GET_GREEN(color) (((color) >> 8) & 0xFF) #define GET_BLUE(color) ((color) & 0xFF) #define SET_ALPHA(color, a) (((color) & 0x00FFFFFF) | ((a) << 24)) #define SET_RED(color, r) (((color) & 0xFF00FFFF) | ((r) << 16)) #define SET_GREEN(color, g) (((color) & 0xFFFF00FF) | ((g) << 8)) #define SET_BLUE(color, b) (((color) & 0xFFFFFF00) | (b)) // 混合两个颜色 uint32_t blendColors(uint32_t c1, uint32_t c2, uint8_t alpha) { uint8_t r = (GET_RED(c1) * alpha + GET_RED(c2) * (255 - alpha)) / 255; uint8_t g = (GET_GREEN(c1) * alpha + GET_GREEN(c2) * (255 - alpha)) / 255; uint8_t b = (GET_BLUE(c1) * alpha + GET_BLUE(c2) * (255 - alpha)) / 255; return (0xFF << 24) | (r << 16) | (g << 8) | b; }

掌握位运算就像获得了一把打开底层编程大门的钥匙。从嵌入式开发到算法优化，这项技能能在许多场景带来意想不到的效果。建议从简单的练习开始，比如实现各种位操作函数，逐步培养对二进制数据的直觉。