二进制与位运算

一句话算法

位运算就是把整数看成一排 0/1 开关，用很少的操作直接检查、打开、关闭或枚举这些开关。

问题模型

一个非负整数可以写成二进制：

13 = 1101(2)

从右往左，最低位编号为 0：

bit:  3 2 1 0
      1 1 0 1

第 $k$ 位的权值是 $2^k$。如果第 $k$ 位是 1，说明这个整数包含 $2^k$ 这一份贡献。

在算法竞赛中，位运算常用于两类问题：

1. 把一个整数当作普通数字处理，例如判断奇偶、取最低位的 1。
2. 把一个整数当作集合状态处理，例如第 $i$ 位表示第 $i$ 个元素是否被选择。

核心直觉

位运算的记忆模型很简单：1 是开，0 是关。

例如要操作第 k 位，最常用的掩码是：

        
1

        1ULL << k
    

它只有第 k 位是 1，其它位都是 0。

基础操作

下面默认 k 从 0 开始，x 是非负整数。

检查第 k 位

        
1

        (x >> k) & 1
    

把第 k 位右移到最低位，再取最低位。

把第 k 位置 1

        
1

        x | (1ULL << k)
    

| 遇到 1 一定变成 1，所以第 k 位会被打开，其它位保持不变。

把第 k 位置 0

        
1

        x & ~(1ULL << k)
    

~(1ULL << k) 只有第 k 位是 0，其它位是 1。和它按位与，就只会关闭第 k 位。

翻转第 k 位

        
1

        x ^ (1ULL << k)
    

^ 1 会翻转，^ 0 会保持不变，所以只翻转第 k 位。

取低 k 位全 1

        
1

        (1ULL << k) - 1
    

例如：

(1 << 4) - 1 = 1111(2)

注意：当 k 等于整数位宽时，1ULL << k 会越界。竞赛代码里要保证 k < 64，或单独处理边界。

lowbit

lowbit(x) 表示只保留 x 二进制中最低位的 1：

        
1

        x & -x
    

例如：

x        = 1011000
lowbit  = 0001000

这个操作在树状数组中非常重要，也常用于枚举一个集合中的元素。

为什么 x & -x 能取到最低位 1

用二进制看，-x 等于 ~x + 1。

设 x 从低位开始，最低的 1 在某个位置：

x    = ?????1000
~x   = ?????0111
~x+1 = ?????1000

最低位 1 右边全是 0，取反后变成全 1，再加 1 正好进位回这个最低的 1。更高位可能变化，但和原数按位与后，只会保留这个最低位 1。

清除最低位 1

        
1

        x & (x - 1)
    

例如：

110100
110011
------
110000

每执行一次，就删掉一个最低位的 1。所以可以用它统计 1 的个数：

        
1
2
3
4
5

        int cnt = 0;
while (x) {
    ++cnt;
    x &= x - 1;
}
    

C++ 中也可以直接使用：

        
1

        __builtin_popcountll(x)
    

最高位

最高位 1 的位置等价于 $\lfloor \log_2 x\rfloor$。

对 unsigned long long，可以用：

        
1

        63 - __builtin_clzll(x)
    

其中 __builtin_clzll(x) 表示从最高位开始连续 0 的数量。注意 x=0 时没有最高位，必须单独处理。

只保留最高位：

        
1

        1ULL << highest_bit_pos(x)
    

清除最高位：

        
1

        x ^ keep_highbit(x)
    

子集枚举

如果 mask 表示一个集合，那么它的子集 sub 必须满足：

        
1

        (sub & mask) == sub
    

常用枚举写法：

        
1
2
3

        for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub 是 mask 的一个非空子集
}
    

如果也要枚举空集，可以在循环外单独处理 0，或者使用：

        
1
2
3
4

        for (int sub = mask;; sub = (sub - 1) & mask) {
    // sub
    if (sub == 0) break;
}
    

为什么 (sub - 1) & mask 能枚举子集

sub - 1 会把最低位的 1 变成 0，并把它右边的位变成 1。这相当于找到下一个更小的二进制状态。

但这个状态可能打开了不属于 mask 的位，所以再 & mask，只保留 mask 中允许出现的位。

这样得到的 sub 每次都严格变小，因此不会重复，并且会走过所有非空子集。

算法步骤

操作某一位

1. 构造掩码 bit = 1ULL << k。
2. 检查：x & bit。
3. 置一：x | bit。
4. 清零：x & ~bit。
5. 翻转：x ^ bit。

统计 1 的数量

1. 令 cnt = 0。
2. 当 x != 0：
   • cnt++。
   • x = x & (x - 1)，清除最低位的 1。
3. cnt 就是二进制中 1 的数量。

枚举子集

1. 令 sub = mask。
2. 处理当前 sub。
3. 更新 sub = (sub - 1) & mask。
4. 当 sub = 0 时停止，或单独处理空集。

算法证明

位操作的正确性

核心不变量：掩码 1ULL << k 只有第 k 位为 1。

• x | mask：第 k 位一定变成 1，其它位与 0 做或运算，不变。
• x & ~mask：第 k 位与 0 做与运算，变成 0，其它位与 1 做与运算，不变。
• x ^ mask：第 k 位与 1 做异或，翻转，其它位与 0 做异或，不变。

所以这三种操作都只影响第 k 位。

清除最低位 1 的正确性

设 $x$ 的最低位 1 右边有 $t$ 个 0：

x     = A 1 00...0
x - 1 = A 0 11...1

按位与后：

x & (x - 1) = A 0 00...0

更高位 A 保持不变，最低位的 1 被清除，右侧仍然是 0。因此每次操作恰好删掉一个 1。

复杂度分析

• 单个位操作：时间复杂度 $O(1)$，空间复杂度 $O(1)$。
• lowbit、清除最低位、判断 $2$ 的幂：时间复杂度 $O(1)$。
• 统计 1 的数量：手写循环为 $O(c)$，其中 $c$ 是 1 的个数；内建函数通常视为 $O(1)$。
• 枚举 mask 的所有子集：若 mask 中有 $c$ 个 1，时间复杂度 $O(2^c)$。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

        #include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

// 第 k 位是否为 1，k 从 0 开始。
bool has_bit(ull x, int k) {
    return (x >> k) & 1ULL;
}

// 把第 k 位置 1。
ull set_bit(ull x, int k) {
    return x | (1ULL << k);
}

// 把第 k 位置 0。
ull clear_bit(ull x, int k) {
    return x & ~(1ULL << k);
}

// 翻转第 k 位。
ull flip_bit(ull x, int k) {
    return x ^ (1ULL << k);
}

// 保留最低位的 1。
ull lowbit(ull x) {
    return x & -x;
}

// 清除最低位的 1。
ull clear_lowbit(ull x) {
    return x & (x - 1);
}

// 统计二进制中 1 的数量。
int count_bits(ull x) {
    return __builtin_popcountll(x);
}

// 最高位 1 的位置，0 没有最高位，返回 -1。
int highest_bit_pos(ull x) {
    if (x == 0) return -1;
    return 63 - __builtin_clzll(x);
}

// 只保留最高位的 1。
ull keep_highbit(ull x) {
    if (x == 0) return 0;
    return 1ULL << highest_bit_pos(x);
}

// 清除最高位的 1。
ull clear_highbit(ull x) {
    return x ^ keep_highbit(x);
}

// 判断是否是 2 的幂。0 不是 2 的幂。
bool is_power_of_two(ull x) {
    return x > 0 && (x & (x - 1)) == 0;
}

// 枚举 mask 的所有非空子集。
vector<ull> non_empty_subsets(ull mask) {
    vector<ull> res;
    for (ull sub = mask; sub; sub = (sub - 1) & mask) {
        res.push_back(sub);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ull x;
    if (!(cin >> x)) return 0;

    cout << "lowbit=" << lowbit(x) << '\n';
    cout << "popcount=" << count_bits(x) << '\n';
    cout << "highest_bit_pos=" << highest_bit_pos(x) << '\n';
    cout << "keep_highbit=" << keep_highbit(x) << '\n';
    cout << "clear_highbit=" << clear_highbit(x) << '\n';
    cout << "is_power_of_two=" << (is_power_of_two(x) ? "yes" : "no") << '\n';

    return 0;
}
    

测试用例

输入：

40

因为：

40 = 101000(2)

输出应包含：

lowbit=8
popcount=2
highest_bit_pos=5
keep_highbit=32
clear_highbit=8
is_power_of_two=no

边界情况：

0

输出中最高位位置为 -1，lowbit 和 keep_highbit 都为 0。

应用分类详解

位运算的本质是“用一个整数保存很多个二值状态”。看到开关状态、集合选择、二进制拆分、奇偶性、低位贡献时，都应该想到位运算。

一、单个数字的二进制性质

典型模式： 题目关心奇偶、是否为 $2$ 的幂、最低位 1、最高位 1、二进制中 1 的数量。

识别信号： 出现“lowbit”“二进制位数”“最高位”“汉明重量”“power of two”。

核心建模： 用位运算直接定位关键位，避免转字符串或循环除法。

二、集合状态压缩

典型模式： 元素数量不大，每个元素只有选或不选两种状态。

识别信号： n <= 20、子集、状态压缩、已访问集合、开关集合。

核心建模： 第 i 位表示第 i 个元素是否被选择，整个集合压成一个 mask。

三、树状数组与低位块

典型模式： 下标要按二进制块跳转。

识别信号： 树状数组、前缀和、i += lowbit(i)、i -= lowbit(i)。

核心建模： lowbit(i) 是下标 i 管理的块长度。更新时跳到下一个包含当前位置的块，查询时不断删掉当前前缀最后一块。

四、枚举优化

典型模式： 需要枚举所有子集或所有补集，但全集规模较小。

识别信号： 对每个集合枚举子集、3^n 复杂度、子集卷积、容斥。

核心建模： 用 (sub - 1) & mask 枚举当前集合的所有子集，只访问合法状态。

经典例题

1. 判断一个数是否是 2 的幂

若 $x>0$ 且：

        
1

        (x & (x - 1)) == 0
    

则 $x$ 的二进制中只有一个 1，所以它是 $2$ 的幂。

2. 树状数组中的 lowbit

树状数组每个节点 i 维护长度为 lowbit(i) 的区间。更新时 i += lowbit(i)，查询时 i -= lowbit(i)，本质都是在二进制块之间跳转。

3. 子集枚举

给定集合 mask，枚举它所有非空子集：

        
1
2
3

        for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // 处理 sub
}
    

这是状态压缩 DP、SOS DP 和容斥计数中的常用基础操作。

参考

• 本书进制转换章节：math/number_base/index.md
• 本书树状数组章节：data_structure/BIT/index.md
• 本书状态压缩 DP 章节：dynamic_programming/binary_state/index.md