第1章 位运算与状态压缩：从零开始玩转二进制

说实话，我刚开始学C语言那会儿，对位运算完全没当回事。觉得不就是几个符号嘛，跟普通运算差不多。直到有一次我在嵌入式项目里写一个LED控制程序，用普通写法代码又长又慢，被老工程师一句话点醒——「你试试位运算」。好家伙，从那以后我就彻底爱上了这种操作方式。

位运算，说白了就是直接操作二进制位。计算机底层全是0和1，你想想看，用位运算就是跟计算机说「方言」，效率能不高吗？今天咱们就从最基础的开始，一步步把位运算吃透。

1.1 位运算基础：与、或、异或、取反、移位

先看一张图，把位运算的几种操作理清楚。我个人习惯把位运算想象成「二进制位的开关游戏」。

上面这张图把六种基本位运算都列出来了。我建议你把它存下来，写代码时随时瞄一眼。下面咱们逐个细说。

1.1.1 按位与（&）

按位与的规则很简单：两个位都是1，结果才是1。这就像两个开关串联，必须都打开灯才亮。

我在项目中常用它来「清零」某些位。比如你想把一个整数的低4位清零，保留高4位，可以这样写：

unsigned char a = 0xAB;  // 1010 1011
unsigned char mask = 0xF0; // 1111 0000
unsigned char result = a & mask; // 1010 0000 = 0xA0

1.1.2 按位或（|）

按位或的规则：只要有一个是1，结果就是1。这相当于并联开关，任何一个闭合灯就亮。

我经常用或运算来「置位」——把某一位强制设为1。比如在GPIO控制中，想把第3位设为1：

unsigned char reg = 0x00;
reg |= (1 << 3);  // 把第3位置1，结果 = 0000 1000

1.1.3 按位异或（^）

异或的规则：相同为0，不同为1。这个操作很有意思，它有个重要性质：a ^ b ^ b = a。说白了，异或两次同一个数，就回到原值。

我记得有一次做数据校验，就用异或来生成简单的校验和。发送方把所有字节异或一遍，接收方再做一次，结果应该是0。如果不对，说明数据传错了。

1.1.4 按位取反（~）

取反就是把所有位翻转：0变1，1变0。注意，它是对整个数的所有位操作，不是只对某一位。

1.1.5 左移（<<）和右移（>>）

左移就是往高位移动，低位补0。每左移一位，相当于乘以2。右移则相反，相当于除以2。但有符号数的右移要注意——高位补的是符号位，不是0。

// 左移示例
int a = 3;      // 0000 0011
int b = a << 2; // 0000 1100 = 12

// 右移示例
int c = 16;     // 0001 0000
int d = c >> 3; // 0000 0010 = 2

1.2 位运算实用技巧

光知道基础操作还不够，得会用。下面这几个技巧，我在实际开发中几乎天天用。

1.2.1 判断奇偶

判断一个数是奇数还是偶数，最直接的方法是用 % 2。但位运算更快：

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

原理很简单：二进制的最低位如果是1，就是奇数；是0就是偶数。你想想看，所有偶数的最低位都是0，对吧？

1.2.2 交换两个数

不用临时变量交换两个数，这个技巧面试经常考：

int a = 5, b = 3;
a = a ^ b;
b = a ^ b;  // b = (a ^ b) ^ b = a
a = a ^ b;  // a = (a ^ b) ^ a = b

不过说实话，我在实际项目中很少这么写。因为可读性差，而且现代编译器对临时变量的优化已经很好了。但作为面试题，你得会。

1.2.3 求绝对值

求绝对值用位运算怎么写？看下面：

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

这段代码的原理是：对于负数，右移31位得到全1（即-1），然后 (n + (-1)) ^ (-1) 等价于取反加1，正好是负数的补码转原码。对于正数，右移31位得到0，结果不变。

1.3 状态压缩DP入门

状态压缩DP，说白了就是用二进制数来表示状态集合。每个二进制位代表一个元素的状态（选或不选、访问或未访问等）。

我最早接触状态压缩DP是在做旅行商问题（TSP）的时候。当时觉得这思路太巧妙了——用一个int就能表示所有城市是否访问过。

1.3.1 基本思想

假设有n个物品，每个物品有「选」和「不选」两种状态。那么所有可能的组合就是2ⁿ种。用一个n位的二进制数就能表示所有状态：

• 第i位为1：表示选了第i个物品
• 第i位为0：表示没选第i个物品

比如n=3时，状态5（二进制101）表示选了第0个和第2个物品，没选第1个。

1.3.2 常用操作

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

// 检查第i位是否为1
if (state & (1 << i)) { ... }

// 将第i位置1
state |= (1 << i);

// 将第i位置0
state &= ~(1 << i);

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

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

1.3.3 经典例子：最短Hamilton路径

给你n个点（n ≤ 20），求从0出发，经过所有点恰好一次，最后回到0的最短路径。这就是状态压缩DP的经典应用。

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f

int dp[1 << 20][20];  // dp[state][i]：状态state下，最后在i点的最短距离
int dist[20][20];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &dist[i][j]);
    
    memset(dp, INF, sizeof(dp));
    dp[1][0] = 0;  // 初始状态：只访问了点0
    
    for (int state = 1; state < (1 << n); state++) {
        for (int i = 0; i < n; i++) {
            if (!(state & (1 << i))) continue;  // i不在当前状态中
            for (int j = 0; j < n; j++) {
                if (state & (1 << j)) continue;  // j已经在状态中
                int next = state | (1 << j);
                if (dp[next][j] > dp[state][i] + dist[i][j]) {
                    dp[next][j] = dp[state][i] + dist[i][j];
                }
            }
        }
    }
    
    printf("%d\n", dp[(1 << n) - 1][0]);
    return 0;
}

这段代码的核心逻辑是：从当前状态state出发，尝试走到下一个未访问的点j，更新状态。最终答案是所有点都访问过（状态为全1）且最后回到0的最短距离。

1.4 避坑指南

最后分享几个我踩过的坑，希望能帮你少走弯路。

• 移位操作的位数不要超过类型宽度： 比如int是32位，你写 1 << 32 是未定义行为。我曾经在循环里没注意边界，结果跑出来的结果完全不对。
• 有符号数的右移： 负数的右移高位补1，不是0。如果你想要逻辑右移（高位补0），用无符号类型。
• 取反操作要小心： ~0 不是0，而是-1（有符号）或最大值（无符号）。我见过有人用 ~0 来清零，结果把整个数都变成-1了。
• 优先级问题： 位运算的优先级比比较运算符低。比如 if (state & (1 << i) == 0) 会先算 ==，结果完全不对。记得加括号。

好了，位运算的基础和状态压缩DP的入门就讲到这里。这些东西看着简单，但用好了威力巨大。下次你写代码时，不妨多想想——「这个操作能不能用位运算搞定？」

---