第39章位运算进阶

课程目录第39章位运算进阶

第39章：位运算进阶——加减乘除、权限管理与优化技巧

位运算这东西，很多初学者觉得它“高冷”，好像只在底层驱动里才有用。其实不然。我做了这么多年C语言开发，可以负责任地告诉你：位运算用好了，代码不仅跑得快，而且能解决很多看似复杂的问题。

今天咱们就深入聊聊位运算的三个核心应用场景：实现加减乘除、权限管理、以及优化技巧。嗯，内容有点干，但绝对值得你花时间啃下来。

一、用位运算实现加减乘除

你可能会问：CPU 不就有加法器吗？为什么还要自己用位运算实现？

其实，理解位运算实现算术运算，能让你真正明白计算机底层是怎么算数的。我在做嵌入式开发时，遇到过没有硬件乘法器的单片机，那时候就得靠位运算来算乘法。说白了，这是基本功。

1. 加法：全加器逻辑

加法是基础中的基础。核心思想就两句话：异或得和，与得进位。

int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;  // 进位
        a = a ^ b;                  // 无进位和
        b = carry;
    }
    return a;
}

举个例子：3 + 5，二进制就是 0011 + 0101。第一次循环，a ^ b = 0110（6），(a & b) << 1 = 0010（2）。第二次循环，6 ^ 2 = 0100（4），进位为 0100 << 1 = 1000（8）。第三次循环，4 ^ 8 = 1100（12），进位为0。搞定。

个人习惯：我写加法函数时，喜欢用 unsigned int 来避免符号位带来的麻烦。尤其是做底层驱动时，符号扩展会让你抓狂。

2. 减法：补码加法

减法其实就是加上一个数的补码。补码怎么算？取反加一。

int sub(int a, int b) {
    return add(a, add(~b, 1));  // a + (-b)
}

嗯，这里要注意：~b + 1 就是 -b 的补码表示。你想想看，CPU 内部其实根本没有减法器，全是靠加法器加补码来完成的。

3. 乘法：移位 + 加法

乘法本质上就是“竖式计算”。二进制乘法比十进制简单多了——每一位要么是0要么是1，所以要么不加，要么加一次移位后的值。

int mul(int a, int b) {
    int result = 0;
    while (b != 0) {
        if (b & 1) {
            result = add(result, a);
        }
        a <<= 1;
        b >>= 1;
    }
    return result;
}

举个例子：3 * 5，二进制 0011 * 0101。b的最低位是1，加a（3）；a左移变6，b右移变2；b最低位是0，不加；a左移变12，b右移变1；b最低位是1，加12，结果15。完美。

我曾经踩过一个坑：在32位系统上做乘法时，忘了考虑溢出。a左移超过31位后，符号位被篡改，结果直接变成负数。所以，做位运算乘法时，建议用 unsigned long long 或者先判断溢出。

4. 除法：减法 + 移位

除法稍微复杂一点。核心思路是：从高位开始，看被除数能不能“容纳”除数的移位版本。

int div(int a, int b) {
    if (b == 0) return -1;  // 除零错误
    int quotient = 0;
    int remainder = a;
    for (int i = 31; i >= 0; i--) {
        if ((remainder >> i) >= b) {
            quotient |= (1 << i);
            remainder = sub(remainder, b << i);
        }
    }
    return quotient;
}

说白了，这就是在模拟我们手算除法的过程。从最高位开始试商，能减就减，商的那一位就置1。

二、位运算实现权限管理

权限管理是位运算最经典的应用之一。我做过一个物联网网关项目，设备有8种不同的操作权限，如果用结构体存，每个用户得占8个字节。用位运算，一个 unsigned char 就够了。

1. 位掩码设计

先定义权限常量，每个权限占一个二进制位：

#define PERM_READ    (1 << 0)  // 0001
#define PERM_WRITE   (1 << 1)  // 0010
#define PERM_EXEC    (1 << 2)  // 0100
#define PERM_DELETE  (1 << 3)  // 1000

2. 权限组合与判断

用 | 组合权限，用 & 判断权限：

unsigned char user_perm = PERM_READ | PERM_WRITE;  // 0011

// 判断是否有读权限
if (user_perm & PERM_READ) {
    printf("有读权限\n");
}

// 添加执行权限
user_perm |= PERM_EXEC;  // 0111

// 删除写权限
user_perm &= ~PERM_WRITE;  // 0101

  核心要点：
  | 添加权限
& ~ 删除权限
& 检查权限
^ 切换权限（有变无，无变有）

你想想看，如果用结构体加布尔变量，你得写多少 if-else？位运算一行搞定，而且速度极快。我在项目中用这种方式管理了32种权限，一个 uint32_t 全搞定，内存占用几乎可以忽略不计。

三、位运算优化技巧

这部分是我个人最喜欢的。很多看似复杂的判断，用位运算几行代码就解决了。面试官也特别喜欢考这些。

1. 判断奇偶

if (n & 1) {
    // 奇数
} else {
    // 偶数
}

比 n % 2 快得多。为什么？因为取模运算在底层要调用除法指令，而位运算一个时钟周期就搞定了。

2. 判断是否为2的幂

int is_power_of_two(unsigned int n) {
    return n && !(n & (n - 1));
}

这个技巧很巧妙。2的幂的二进制只有一个1，比如 1000。减1后变成 0111，两者按位与结果为0。如果不是2的幂，比如 1010，减1后是 1001，与的结果不为0。

3. 交换两个变量

a ^= b;
b ^= a;
a ^= b;

不需要临时变量，三行异或搞定。不过说实话，在现代CPU上，这个技巧的性能优势已经不明显了，编译器优化后的代码可能更快。但面试时写出来，能体现你对位运算的理解。

4. 取绝对值

int abs(int x) {
    int mask = x >> (sizeof(int) * 8 - 1);
    return (x + mask) ^ mask;
}

这个稍微有点绕。mask 是符号位的扩展：正数 mask=0，负数 mask=-1（全1）。x + mask 对于负数相当于减1，再异或 mask（全1）相当于取反。说白了，就是补码转原码的过程。

我建议：这些优化技巧，在性能敏感的场景下大胆用。但在普通业务代码里，还是以可读性为主。毕竟代码是写给人看的，机器只是顺便执行。

5. 状态压缩

假设你有8个布尔状态，用8个变量存太浪费了。一个 unsigned char 就够了：

unsigned char flags = 0;

// 设置第3个状态
flags |= (1 << 2);

// 清除第5个状态
flags &= ~(1 << 4);

// 检查第0个状态
if (flags & 1) { ... }

// 切换第1个状态
flags ^= (1 << 1);

我在做嵌入式协议栈时，用这种方式管理了十几个连接状态。一个 uint16_t 搞定所有标志位，而且操作起来比结构体快得多。

总结一下

位运算不是花架子，它是C语言里最接近硬件的操作之一。加减乘除的实现让你理解CPU的工作原理，权限管理让你写出更优雅的代码，优化技巧则能在关键时刻提升性能。

嗯，最后说一句：面试时如果被问到位运算，别只背答案。把背后的原理讲清楚，再结合你项目中的实际应用，面试官一定会对你刮目相看。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录