位操作是 C 语言的核心技能之一，能够高效地处理底层数据、进行权限控制、实现位图数据结构等。本文详细介绍位运算符、位域、位掩码与位图操作的实战技巧。
位运算符基础
C 语言提供了六种位运算符，用于直接操作二进制位：
bit_operators.c
// 位运算符示例 #includevoid printBinary(unsigned int n) { for (int i = 31; i >= 0; i--) { printf("%d", (n >> i) & 1); if (i % 8 == 0) printf(" "); } printf("\n"); } int main() { unsigned int a = 0b11010110; // 214 unsigned int b = 0b00101101; // 45 printf("a = "); printBinary(a); printf("b = "); printBinary(b); // 按位与 printf("a & b = "); printBinary(a & b); // 按位或 printf("a | b = "); printBinary(a | b); // 按位异或 printf("a ^ b = "); printBinary(a ^ b); // 按位取反 printf("~a = "); printBinary(~a); // 左移 printf("a << 2 = "); printBinary(a << 2); // 右移 printf("a >> 2 = "); printBinary(a >> 2); return 0; }
位掩码操作
位掩码是操作特定位的核心技术，广泛应用于标志位、权限控制等场景：
bitmask.c
// 位掩码操作 #include#include // 定义标志位掩码 #define FLAG_READ (1 << 0) // 0x01 #define FLAG_WRITE (1 << 1) // 0x02 #define FLAG_EXEC (1 << 2) // 0x04 #define FLAG_SYNC (1 << 3) // 0x08 #define FLAG_CACHE (1 << 4) // 0x10 // 设置标志位 void setFlag(uint32_t *flags, uint32_t flag) { *flags |= flag; } // 清除标志位 void clearFlag(uint32_t *flags, uint32_t flag) { *flags &= ~flag; } // 切换标志位 void toggleFlag(uint32_t *flags, uint32_t flag) { *flags ^= flag; } // 检查标志位 int checkFlag(uint32_t flags, uint32_t flag) { return (flags & flag) != 0; } // 获取多位域的值 uint32_t getBitField(uint32_t value, int start, int bits) { return (value >> start) & ((1 << bits) - 1); } // 设置多位域的值 void setBitField(uint32_t *value, uint32_t newValue, int start, int bits) { uint32_t mask = ((1 << bits) - 1); *value = (*value & ~(mask << start)) | ((newValue & mask) << start); } int main() { uint32_t flags = 0; // 设置权限标志 setFlag(&flags, FLAG_READ | FLAG_WRITE); printf("设置读写标志: 0x%08X\n", flags); // 检查标志 printf("可读: %s\n", checkFlag(flags, FLAG_READ) ? "是" : "否"); printf("可执行: %s\n", checkFlag(flags, FLAG_EXEC) ? "是" : "否"); // 切换标志 toggleFlag(&flags, FLAG_EXEC); printf("切换执行标志后: 0x%08X\n", flags); printf("可执行: %s\n", checkFlag(flags, FLAG_EXEC) ? "是" : "否"); // 清除标志 clearFlag(&flags, FLAG_WRITE); printf("清除写标志后: 0x%08X\n", flags); // 位域操作示例 uint32_t packet = 0x12345678; printf("\n位域操作示例\n"); printf("原始值: 0x%08X\n", packet); // 获取第4-7位（4位） uint32_t field = getBitField(packet, 4, 4); printf("第4-7位: 0x%X\n", field); // 设置第4-7位为 0xA setBitField(&packet, 0xA, 4, 4); printf("设置后: 0x%08X\n", packet); return 0; }
位域结构体
位域允许在结构体中定义占用特定位数成员：
bitfield.c
// 位域结构体 #include#include // TCP 头部（简化版） struct tcp_header { uint16_t src_port; // 16位源端口 uint16_t dst_port; // 16位目的端口 uint32_t seq_num; // 32位序列号 uint32_t ack_num; // 32位确认号 uint8_t data_offset; // 4位数据偏移 uint8_t flags; // 8位标志 uint16_t window; // 16位窗口大小 uint16_t checksum; // 16位校验和 uint16_t urgent; // 16位紧急指针 }; // 使用位域定义 IP 头部 struct ip_header_bitfield { uint8_t version: 4; // 4位版本 uint8_t ihl: 4; // 4位头长度 uint8_t tos; // 8位服务类型 uint16_t total_length; // 16位总长度 uint16_t id; // 16位标识 uint8_t flags: 3; // 3位标志 uint16_t fragment_offset: 13; // 13位片偏移 uint8_t ttl; // 8位生存时间 uint8_t protocol; // 8位协议 uint16_t checksum; // 16位头校验和 uint32_t src_addr; // 32位源地址 uint32_t dst_addr; // 32位目的地址 }; // 使用联合体访问位域或原始字节 union IPHeader { struct ip_header_bitfield bits; uint8_t bytes[20]; }; void printIPHeader(struct ip_header_bitfield *ip) { printf("Version: %d\n", ip->version); printf("Header Length: %d words (%d bytes)\n", ip->ihl, ip->ihl * 4); printf("Type of Service: 0x%02X\n", ip->tos); printf("Total Length: %d bytes\n", ip->total_length); printf("ID: 0x%04X\n", ip->id); printf("Flags: 0x%X\n", ip->flags); printf("Fragment Offset: %d\n", ip->fragment_offset); printf("TTL: %d\n", ip->ttl); printf("Protocol: %d\n", ip->protocol); } int main() { // 创建 IP 头 struct ip_header_bitfield ip = { .version = 4, .ihl = 5, .tos = 0, .total_length = 60, .id = 0x1234, .flags = 0, .fragment_offset = 0, .ttl = 64, .protocol = 6, .checksum = 0, }; printIPHeader(&ip); // 通过联合体访问原始字节 printf("\n原始字节:\n"); union IPHeader header; header.bits = ip; for (int i = 0; i < 20; i++) { printf("%02X ", header.bytes[i]); if ((i + 1) % 4 == 0) printf("\n"); } return 0; }
位图数据结构
位图（Bitmap）是一种高效的稀疏数据结构，特别适合需要快速查找和去重的场景：
bitmap.c
// 位图实现 #include#include #include #include #define BITS_PER_WORD 32 #define WORD_INDEX(n) ((n) / BITS_PER_WORD) #define BIT_OFFSET(n) ((n) % BITS_PER_WORD) typedef struct { uint32_t *bits; size_t size; } Bitmap; // 创建位图 Bitmap *bitmapCreate(size_t maxBits) { Bitmap *bm = (Bitmap *)malloc(sizeof(Bitmap)); if (!bm) return NULL; bm->size = (WORD_INDEX(maxBits) + 1); bm->bits = (uint32_t *)calloc(bm->size, sizeof(uint32_t)); if (!bm->bits) { free(bm); return NULL; } return bm; } // 释放位图 void bitmapFree(Bitmap *bm) { if (bm) { free(bm->bits); free(bm); } } // 设置位 void bitmapSet(Bitmap *bm, size_t pos) { if (pos >= bm->size * BITS_PER_WORD) return; bm->bits[WORD_INDEX(pos)] |= (1U << BIT_OFFSET(pos)); } // 清除位 void bitmapClear(Bitmap *bm, size_t pos) { if (pos >= bm->size * BITS_PER_WORD) return; bm->bits[WORD_INDEX(pos)] &= ~(1U << BIT_OFFSET(pos)); } // 测试位 int bitmapTest(Bitmap *bm, size_t pos) { if (pos >= bm->size * BITS_PER_WORD) return 0; return (bm->bits[WORD_INDEX(pos)] & (1U << BIT_OFFSET(pos))) != 0; } // 查找第一个未设置的位 int bitmapFindFree(Bitmap *bm, size_t *pos) { for (size_t i = 0; i < bm->size; i++) { if (bm->bits[i] != 0xFFFFFFFF) { // 找到有空闲位的字 for (uint32_t j = 0; j < BITS_PER_WORD; j++) { if (!(bm->bits[i] & (1U << j))) { *pos = i * BITS_PER_WORD + j; return 0; } } } } return -1; } // 统计设置的位数 size_t bitmapCount(Bitmap *bm) { size_t count = 0; for (size_t i = 0; i < bm->size; i++) { uint32_t word = bm->bits[i]; // 使用 Brian Kernighan 算法 while (word) { word &= (word - 1); count++; } } return count; } int main() { // 创建能存储 1000 个状态的位图 Bitmap *bm = bitmapCreate(1000); if (!bm) { printf("位图创建失败\n"); return 1; } // 设置一些位 bitmapSet(bm, 5); bitmapSet(bm, 10); bitmapSet(bm, 100); bitmapSet(bm, 500); printf("已设置 %zu 个位置\n", bitmapCount(bm)); printf("位置 5 已设置: %s\n", bitmapTest(bm, 5) ? "是" : "否"); printf("位置 6 已设置: %s\n", bitmapTest(bm, 6) ? "是" : "否"); // 查找第一个空闲位置 size_t freePos; if (bitmapFindFree(bm, &freePos) == 0) { printf("第一个空闲位置: %zu\n", freePos); } // 清除位 5 bitmapClear(bm, 5); printf("清除位置 5 后，已设置 %zu 个位置\n", bitmapCount(bm)); bitmapFree(bm); return 0; }
位操作技巧
一些常用的位操作技巧：
bit_tricks.c
// 位操作技巧 #include#include // 判断是否为2的幂 int isPowerOfTwo(uint32_t n) { return n != 0 && (n & (n - 1)) == 0; } // 获取最高的设置位 int highestBit(uint32_t n) { int pos = -1; while (n > 0) { n >>= 1; pos++; } return pos; } // 计算 2 的幂的指数 int log2(uint32_t n) { int pos = 0; while (n > 1) { n >>= 1; pos++; } return pos; } // 四舍五入到最接近的2的幂 uint32_t roundToPowerOfTwo(uint32_t n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; } // 交换两个数（不使用临时变量） void swap(int *a, int *b) { *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } // 判断符号是否相同 int sameSign(int a, int b) { return (a ^ b) >= 0; } // 计算绝对值（无分支） int abs(int n) { int mask = n >> (sizeof(int) * 8 - 1); return (n + mask) ^ mask; } // Brian Kernighan 算法：统计设置位数 int countBits(uint32_t n) { int count = 0; while (n) { n &= (n - 1); count++; } return count; } // 检查第 n 位是否设置 int checkBit(uint32_t n, int bit) { return (n & (1 << bit)) != 0; } // 设置第 n 位 uint32_t setBit(uint32_t n, int bit) { return n | (1 << bit); } // 清除第 n 位 uint32_t clearBit(uint32_t n, int bit) { return n & ~(1 << bit); } int main() { printf("isPowerOfTwo(8): %s\n", isPowerOfTwo(8) ? "true" : "false"); printf("isPowerOfTwo(10): %s\n", isPowerOfTwo(10) ? "true" : "false"); printf("highestBit(256): %d\n", highestBit(256)); printf("log2(256): %d\n", log2(256)); printf("roundToPowerOfTwo(100): %u\n", roundToPowerOfTwo(100)); int x = 5, y = 10; swap(&x, &y); printf("swap(5, 10): x=%d, y=%d\n", x, y); printf("countBits(255): %d\n", countBits(255)); return 0; }
总结
位操作是 C 语言的强大特性：
- 位运算符：按位与、或、异或、取反、左移、右移
- 位掩码：高效设置、清除、切换和检查特定位
- 位域：在结构体中定义占用特定位数的成员
- 位图：高效的稀疏数据结构和快速查找实现
- 位操作技巧：判断2的幂、统计位数、交换变量等
熟练掌握位操作能够编写出更高效、更节省内存的代码。