第24章位运算算法

课程目录第24章位运算算法

第24章位运算算法：从基础到状态压缩DP

位运算，说白了就是直接操作二进制位。很多初学者觉得这东西太底层，平时用不上。但我做了十几年嵌入式开发，可以负责任地告诉你——位运算恰恰是C语言里最实用的技巧之一。寄存器配置、数据压缩、性能优化，哪哪都离不开它。

这一章，我会带你从最基础的位运算操作讲起，再到常用技巧，最后聊聊状态压缩DP。嗯，内容不少，但都很实用。

24.1 位运算基础

C语言提供了6种位运算符。我习惯把它们分成两组：逻辑运算和移位运算。

24.1.1 与、或、异或、取反

先看个表格，一目了然：

运算符	名称	规则	记忆口诀
&	按位与	两个都为1才为1	有0则0
\|	按位或	一个为1即为1	有1则1
^	按位异或	相同为0，不同为1	相同则0
~	按位取反	0变1，1变0	全部翻转

举个例子，假设 a = 0b1100（十进制12），b = 0b1010（十进制10）：

a & b  = 0b1000  (8)
a | b  = 0b1110  (14)
a ^ b  = 0b0110  (6)
~a     = 0b0011  (3)   // 假设只取低4位

我在项目中遇到过一个问题：用位与来快速判断一个数是不是2的幂。你想想看，2的幂在二进制里只有一个1，比如4是0b100，8是0b1000。那么 n & (n-1) 如果等于0，就说明n是2的幂。这个技巧我在协议解析里经常用。

24.1.2 左移和右移

左移 << 和右移 >> 也很简单：

左移：高位丢弃，低位补0。相当于乘以2的n次方。
右移：对于无符号数，高位补0；对于有符号数，高位补符号位（算术右移）。

unsigned char x = 0b00000101;  // 5
x << 2 = 0b00010100;          // 20，相当于5*4
x >> 1 = 0b00000010;          // 2，相当于5/2（向下取整）

注意：有符号数的右移行为是编译器相关的。我曾经在移植代码时踩过这个坑——一个负数右移，有的编译器补0，有的补1，结果程序跑飞了。所以，有符号数尽量别用右移，或者先转成无符号再操作。

24.2 常用技巧

这些技巧我几乎每天都在用。你学会了，写代码会快很多。

24.2.1 判断奇偶

传统做法是用 % 2，但位运算更快：

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

原理很简单：二进制最低位是1就是奇数，是0就是偶数。这个判断在嵌入式里特别有用，因为取模运算在某些单片机上是软实现的，慢得很。

24.2.2 交换两个数

不用临时变量，用异或就能交换：

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

为什么能行？因为异或有个性质：x ^ x = 0，x ^ 0 = x。你推导一下就明白了。不过我个人建议，日常开发还是用临时变量，可读性更好。这个技巧在面试里出现得多，实际项目中我很少用——万一a和b是同一个变量，结果就变成0了。

24.2.3 求绝对值

这个技巧稍微绕一点，但很巧妙：

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

解释一下：如果x是正数，mask=0，结果就是x；如果x是负数，mask=-1（全1），x+(-1)相当于x-1，再异或-1相当于取反，正好得到绝对值。嗯，这个我建议你背下来，面试常考。

我的经验：位运算技巧虽然酷，但别滥用。代码首先是给人看的，其次才是给机器跑的。只有在性能瓶颈处才用这些技巧，平时写清楚比写快更重要。

24.3 状态压缩DP

终于到了重头戏。状态压缩DP，说白了就是用二进制位来表示状态。每个位代表一个元素选或不选，一个整数就能表示一个集合。

24.3.1 为什么需要状态压缩？

你想想看，如果我们要表示一个集合，比如{1, 3, 5}，用数组当然可以。但有些问题需要枚举所有子集，比如旅行商问题（TSP），n个城市就有2^n种状态。用数组存？太浪费了。用整数存？一个int就够了。

举个例子，n=5时，状态0b10101表示选择了第0、2、4个元素（从低位开始数）。

24.3.2 常用操作

状态压缩DP里，这几个操作是基本功：

// 检查第i位是否为1
if (mask & (1 << i))

// 将第i位设为1
mask |= (1 << i)

// 将第i位设为0
mask &= ~(1 << i)

// 翻转第i位
mask ^= (1 << i)

// 枚举所有子集
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // 处理子集sub
}

最后一个枚举子集的写法很经典。我刚开始学的时候也看不懂，后来画了个二进制图才明白——每次减1再与上原集合，就能遍历所有子集。这个技巧在DP里经常用到。

24.3.3 经典问题：最短Hamilton路径

给你n个点（n≤20），求从0出发，经过每个点恰好一次，最后回到0的最短路径。这就是旅行商问题的简化版。

状态定义：dp[mask][i] 表示已经访问过的点集为mask，当前在点i的最短距离。

int dp[1 << N][N];
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;  // 从0出发，只访问了0

for (int mask = 1; mask < (1 << N); mask++) {
    for (int i = 0; i < N; i++) {
        if (!(mask & (1 << i))) continue;  // i不在集合中
        for (int j = 0; j < N; j++) {
            if (mask & (1 << j)) continue;  // j已经在集合中
            int next = mask | (1 << j);
            dp[next][j] = min(dp[next][j], dp[mask][i] + dist[i][j]);
        }
    }
}
// 最后回到0
int ans = INF;
for (int i = 1; i < N; i++) {
    ans = min(ans, dp[(1 << N) - 1][i] + dist[i][0]);
}

这个代码里，mask从1遍历到(1<<N)-1，每个状态都尝试扩展。时间复杂度O(n²·2ⁿ)，对于n=20来说，大约4亿次操作，优化一下能过。

核心思想：状态压缩DP的本质就是用整数代替集合，用位运算代替集合操作。你掌握了这个思路，很多看似复杂的问题都能迎刃而解。

24.3.4 状态压缩DP的SVG流程图

下面这张图展示了状态压缩DP的核心流程：

24.4 避坑指南

讲了这么多，最后分享几个我踩过的坑：

优先级问题：位运算的优先级比比较运算符低。比如 if (mask & (1<<i) == 0) 会先算 (1<<i)==0，结果永远为假。一定要加括号：if ((mask & (1<<i)) == 0)。
移位溢出：1<<31 在int里是合法的，但1<<32就未定义了。我建议用 (1ULL << i) 来避免问题。
有符号右移：前面说过了，尽量用无符号数做右移。
状态压缩DP的数组大小：1<<20 是1048576，再大一点内存就爆了。所以n一般不超过20。

我曾经在一个项目里用状态压缩DP解决任务调度问题，n=15，状态数32768，跑起来飞快。后来需求改成n=25，直接内存溢出。嗯，这就是位运算的边界——它很快，但容量有限。

好了，这一章的内容就到这里。位运算看似简单，但用好了能写出非常优雅的代码。你平时写代码时，可以刻意练习一下，把能用位运算的地方都改一改，慢慢就熟练了。

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

📚 课程目录