位运算及其应用实例（二）

編輯：關於C語言

位运算进阶技巧：掩码、交换、幂次判断与权限模型

位运算是贴近硬件的高效操作，掌握常用位技巧能写出简洁且极快的代码。

1. 常用位掩码模式

// 第 k 位置 1：  x |= (1U << k)
// 第 k 位清 0：  x &= ~(1U << k)
// 第 k 位翻转：  x ^= (1U << k)
// 测试第 k 位： (x >> k) & 1U
// 取低 k 位：   x & ((1U << k) - 1)
// 清零最低位 1： x & (x - 1)   // 核心技巧：x & (x-1) 删除最右侧的 1
// 仅保留最低位 1： x & (-x)    // 利用补码特性

2. 无临时变量交换（异或交换）

void xor_swap(int *a, int *b) {
    if (a != b) { *a ^= *b; *b ^= *a; *a ^= *b; }
}

注意：现代编译器优化下，临时变量版本往往更快且无别名问题，异或交换主要用于教学或寄存器极度受限的嵌入式场景。

3. 2 的幂次判断与对齐

bool is_pow2(unsigned x) { return x && !(x & (x - 1)); }
// 向上对齐到 2^n 边界
unsigned align_up(unsigned x, unsigned n) { return (x + n - 1) & ~(n - 1); }

4. 位图：紧凑布尔集合

typedef unsigned long bitmap_t;
#define BITSET(b, i)   ((b)[(i)/64] |= 1UL << ((i)%64))
#define BITCLR(b, i)   ((b)[(i)/64] &= ~(1UL << ((i)%64)))
#define BITTEST(b, i)  ((b)[(i)/64] &  (1UL << ((i)%64)))

bitmap_t bits[1024] = {0};  // 65536 位
BITSET(bits, 12345);
if (BITTEST(bits, 12345)) { /* ... */ }

位图广泛用于内存分配器空闲块管理、数据库索引、Bloom Filter 等。

5. 权限/标志位模型

enum Perm { READ = 1<<0, WRITE = 1<<1, EXEC = 1<<2, ADMIN = 1<<3 };
unsigned user_perm = READ | WRITE;  // 组合权限
if (user_perm & WRITE) { /* 可写 */ }
user_perm |= EXEC;                  // 授予执行权
user_perm &= ~READ;                 // 撤销读权

Linux chmod、文件打开标志 O_RDWR | O_CREAT、网络协议标志位均采用此模式。

6. 计数人口数与前导零

// GCC/Clang 内置函数，编译为单指令
int cnt = __builtin_popcount(x);      // 32-bit
int cnt = __builtin_popcountll(x);    // 64-bit
int lz  = __builtin_clz(x);           // leading zeros
int tz  = __builtin_ctz(x);           // trailing zeros

这些内置函数在 x86 上映射为 POPCNT、LZCNT/BSR、TZCNT/BSF 指令，极高效。

7. 实战案例：快速哈希与校验和

// FNV-1a 32-bit
uint32_t fnv1a(const void *data, size_t len) {
    uint32_t h = 0x811c9dc5;
    const uint8_t *p = data;
    while (len--) { h ^= *p++; h *= 0x01000193; }
    return h;
}

// Adler-32 校验和（zlib 使用）
uint32_t adler32(const void *data, size_t len) {
    uint32_t a = 1, b = 0;
    const uint8_t *p = data;
    while (len--) { a = (a + *p++) % 65521; b = (b + a) % 65521; }
    return (b << 16) | a;
}