算法刷题系列（五）：位运算——用二进制表达状态

算法刷题系列（五）：位运算——用二进制表达状态

在前面的数学篇中，我们用余数描述周期状态。位运算提供了另一种紧凑的状态表示：如果每个状态只有“是/否”两种可能，就可以用一个二进制位表示它。

本篇从“记录一组开关的开闭状态”开始，解释掩码、检查位、设置位、清除位和翻转位，并用 Java 与 Python 实现。下一篇会把这种位掩码用于枚举一个小集合的所有子集。

一、二进制位与掩码

一个整数可以看成若干个二进制位组成。以 8 位表示为例：

十进制：13
二进制：00001101

从右向左，位的位置从 0 开始编号：

位编号：  7 6 5 4 3 2 1 0
二进制：  0 0 0 0 1 1 0 1

可以用一个整数 mask 表示多个布尔状态。例如有 4 个开关，编号为 0 到 3，第 i 位为 1 表示开关 i 开启，为 0 表示关闭。

如果开关 0 和开关 2 开启，掩码为：

mask = 0101₂ = 5

位掩码本质上是把一组布尔值压缩进整数。它适合状态数量较小、每个状态只有两种取值的问题；它不适合直接保存任意计数或需要大量独立状态的场景。

二、四种常用位操作

要操作第 i 位，先构造只在该位为 1 的掩码：

bit = 1 << i

假设 mask 记录开关状态。

1. 检查第 i 位是否为 1

(mask & (1 << i)) != 0

按位与会把不同时为 1 的位清零。如果结果不为零，说明目标位原来是 1。

2. 设置第 i 位

mask | (1 << i)

按位或会把目标位设为 1，其他位保持不变。重复设置同一位仍然是 1，所以这是幂等操作。

3. 清除第 i 位

mask & ~(1 << i)

~ 会反转掩码的位，按位与后目标位变成 0，其他位保留原值。

4. 翻转第 i 位

mask ^ (1 << i)

按位异或中，两个位相同结果为 0，不同结果为 1，因此目标位会在 0 和 1 之间切换。

三、原创例子：维护设备功能开关

假设一个小型控制面板有四项功能：

功能	编号
照明	0
风扇	1
报警器	2
自动模式	3

现在需要执行以下操作：

1. 开启照明；
2. 开启报警器；
3. 检查风扇是否开启；
4. 关闭照明；
5. 翻转自动模式。

初始状态为 0000₂。开启照明和报警器后：

0000₂ | 0001₂ = 0001₂
0001₂ | 0100₂ = 0101₂

此时报警器开启，风扇关闭。接下来关闭照明：

0101₂ & 1110₂ = 0100₂

翻转自动模式（第 3 位）：

0100₂ ^ 1000₂ = 1100₂

最终状态为 1100₂，表示报警器和自动模式开启。

四、Java 实现

public class FeatureFlags {
    private static final int LIGHT = 0;
    private static final int FAN = 1;
    private static final int ALARM = 2;
    private static final int AUTO_MODE = 3;

    public static boolean isEnabled(int mask, int feature) {
        return (mask & (1 << feature)) != 0;
    }

    public static int enable(int mask, int feature) {
        return mask | (1 << feature);
    }

    public static int disable(int mask, int feature) {
        return mask & ~(1 << feature);
    }

    public static int toggle(int mask, int feature) {
        return mask ^ (1 << feature);
    }

    public static void main(String[] args) {
        int mask = 0;
        mask = enable(mask, LIGHT);
        mask = enable(mask, ALARM);

        boolean fanEnabled = isEnabled(mask, FAN);
        mask = disable(mask, LIGHT);
        mask = toggle(mask, AUTO_MODE);

        System.out.println(fanEnabled); // false
        System.out.println(Integer.toBinaryString(mask)); // 1100
    }
}

实际代码中，如果 feature 来自外部输入，应先验证它位于允许范围内。Java 的 int 只有固定数量的位，移位距离也会按类型规则处理；不要把任意大下标直接传给移位表达式。

五、Python 实现

LIGHT = 0
FAN = 1
ALARM = 2
AUTO_MODE = 3

def is_enabled(mask: int, feature: int) -> bool:
    return (mask & (1 << feature)) != 0

def enable(mask: int, feature: int) -> int:
    return mask | (1 << feature)

def disable(mask: int, feature: int) -> int:
    return mask & ~(1 << feature)

def toggle(mask: int, feature: int) -> int:
    return mask ^ (1 << feature)

mask = 0
mask = enable(mask, LIGHT)
mask = enable(mask, ALARM)

fan_enabled = is_enabled(mask, FAN)
mask = disable(mask, LIGHT)
mask = toggle(mask, AUTO_MODE)

assert fan_enabled is False
assert format(mask, "04b") == "1100"

Python 整数可以保存任意多个位，因此位数不会像 Java int 那样固定；不过非常大的整数依然会消耗更多资源，且需要确认问题是否真的适合位掩码表示。

六、常用位技巧

判断奇偶

最低位为 1 表示奇数，为 0 表示偶数：

n & 1

移除最低位的 1

对于正整数 n：

n & (n - 1)

这个操作会清除最右边（最低位）的那个 1。例如：

101100₂
101011₂
------- &
101000₂

重复执行，可以统计二进制表示中 1 的个数。许多语言也提供内置的 bit count 函数；题目允许使用时优先考虑标准库，避免重写易错的底层细节。

提取最低位的 1

对于正整数 n，n & -n 会保留最低位的 1，其余位清零。它的推导依赖固定宽度整数的补码表示；在具体语言和整数类型中使用前，应确认相应规则。

七、复杂度与适用边界

对固定宽度整数执行单个位的检查、设置、清除或翻转，通常可视为 O(1) 时间和 O(1) 额外空间。

但要注意：

• 位掩码可表示的状态数随位数指数增长。k 个开关有 2^k 种组合状态。
• 单个整数能保存多少位取决于语言和类型；Java int、long 是固定宽度，Python 整数是可扩展精度。
• 如果某个状态需要三种以上取值，单个位不够，需要重新设计编码或使用数组/映射。
• 位运算代码短不等于更易读。对于大型业务开关集合，命名清楚的集合或枚举结构可能更合适。

八、常见错误

1. 位编号从 1 开始却按 0 开始实现：先明确题目中的编号与代码中的位偏移如何对应。
2. 混淆 | 和 ^：| 是确保开启，^ 是翻转；重复执行的结果不同。
3. 忘记括号：像 (mask & bit) != 0 这样的写法可读性更好，也避免运算优先级误解。
4. 对负数直接套“二进制字符串”直觉：固定宽度整数使用补码，负数的按位操作要结合类型宽度分析。
5. 忽略移位范围：移位距离越界时，不同语言的行为不同，需按语言规则处理。
6. 误以为位掩码可以无成本表示很多开关：表示一个掩码很省空间，但枚举所有组合仍是指数级。

九、从位运算到二进制枚举

如果 k 个开关各自只有开/关两种状态，那么所有可能状态正好是 2^k 个。每个状态都可以用一个从 0 到 2^k - 1 的整数表示：

000₂  空集合
001₂  只选第 0 项
010₂  只选第 1 项
011₂  选第 0、1 项
...

这就把位运算自然连接到下一篇：遍历所有掩码，枚举集合的每一种子集。枚举前必须先看规模，因为 k 增加 1，候选状态数量就翻倍。

小结

位运算能直接检查或修改整数中的二进制位。先用 1 << i 构造目标位，再根据需求使用按位与、或、取反和异或。位掩码适合表示数量较少的布尔状态；当需要遍历所有组合时，复杂度会达到 O(2^k)，不能仅凭表示紧凑就忽视状态空间的指数增长。