《算法竞赛进阶指南》0x01小节：位运算

一、小节概述

位运算是计算机底层操作的核心，在算法竞赛中广泛应用于状态压缩、快速计算、位图存储等场景。

学习目标：

1. 掌握二进制表示与位运算基本操作
2. 理解并熟练使用位运算常用技巧
3. 能够应用位运算解决实际问题
4. 理解状态压缩的基本思想

建议学时：6h

二、核心知识点详解

1. 二进制基础回顾

1.1 二进制表示与编码方式

计算机中整数有三种表示方式：原码、反码、补码。以8位二进制为例进行详细说明：

1. 原码 (Sign-Magnitude)

• 定义：最高位为符号位（0表示正数，1表示负数），其余位表示数值的绝对值
• 8位原码举例：
  • +5 的原码：0000 0101（最高位0表示正，后7位000 0101表示5）
  • -5 的原码：1000 0101（最高位1表示负，后7位000 0101表示5）
• 表示范围：-127 ~ +127
  • 最大正数：0111 1111 = +127
  • 最小负数：1111 1111 = -127
• 存在问题：
  1. 两种零表示：+0=0000 0000 和 -0=1000 0000
  2. 加减运算复杂：需要判断符号位，同号相加，异号相减
  3. 硬件实现复杂：需要额外的符号位处理电路

2. 反码 (Ones' Complement)

• 定义：
  • 正数：反码与原码相同
  • 负数：符号位保持为1，数值位按位取反（0变1，1变0）
• 计算过程（以-5为例）：
  1. 先求+5的原码：0000 0101
  2. 符号位置1：1000 0101
  3. 数值位取反：1111 1010
• 8位反码举例：
  • +5 的反码：0000 0101
  • -5 的反码：1111 1010
  • +0 的反码：0000 0000
  • -0 的反码：1111 1111
• 运算特点：减法可通过加法实现，但需要处理循环进位（end-around carry）
• 仍然存在的问题：两种零表示的问题未解决

3. 补码 (Two's Complement) - 现代计算机标准

• 定义：

  • 正数：补码与原码、反码相同
  • 负数：反码 + 1

• 计算过程（三种方法）： 方法1（标准方法）：

  1. 求绝对值的原码（如5→0000 0101）
  2. 按位取反得反码（1111 1010）
  3. 加1得补码（1111 1011）

  方法2（简便方法）：

  • 从右向左找到第一个1，这个1及其右边的位保持不变，左边的位全部取反
  • 例如-5：0000 0101 → 从右第一个1是最低位 → 左边全取反 → 1111 1011

  方法3（数学方法）：

  • 对于n位补码：负数 = 2^n - |负数|
  • 8位-5：256 - 5 = 251 = 1111 1011

• 8位补码重要值：

  • +5：0000 0101
  • -5：1111 1011
  • +0/-0：0000 0000（唯一零表示）
  • -1：1111 1111
  • -128：1000 0000（特殊值，没有对应的正数）
  • 最大正数：0111 1111 = +127
  • 最小负数：1000 0000 = -128

• 补码的数学原理： 对于n位补码，数值计算公式为： [ \text{值} = -2^{n-1} \times b_{n-1} + \sum_{i=0}^{n-2} 2^i \times b_i ] 其中(b_{n-1})是符号位。

  以1111 1011(-5)为例：

  • 符号位：1 → -2^7 × 1 = -128
  • 数值位：1×2^6 + 1×2^5 + 1×2^4 + 1×2^3 + 0×2^2 + 1×2^1 + 1×2^0 = 64+32+16+8+0+2+1 = 123
  • 总和：-128 + 123 = -5

• 补码的核心优势：

  1. 唯一零表示：解决了±0问题
  2. 减法变加法：A - B = A + (-B的补码)，硬件只需实现加法器
  3. 符号位参与运算：无需特殊处理符号位
  4. 表示范围对称：-128~127（比原码多表示一个数）

4. 补码运算示例

• 计算 5 + (-3)：

    5: 0000 0101
  +(-3):1111 1101  (3=0000 0011，取反=1111 1100，加1=1111 1101)
  -----------------
          0000 0010 = 2 ✓
  进位：1 0000 0010（最高位进位丢弃）
  

• 计算 5 - 7 = 5 + (-7)：

    5: 0000 0101
  +(-7):1111 1001  (7=0000 0111，取反=1111 1000，加1=1111 1001)
  -----------------
          1111 1110 = -2 ✓
  

5. 无符号整数

• 定义：所有位都表示数值，没有符号位
• 8位无符号范围：0 ~ 255
• 同一二进制模式的不同解释：
  • 1111 1011：
    • 有符号解释：补码 = -5
    • 无符号解释：1×2^7 + 1×2^6 + 1×2^5 + 1×2^4 + 1×2^3 + 0×2^2 + 1×2^1 + 1×2^0 = 128+64+32+16+8+0+2+1 = 251
• 类型转换注意：C/C++中类型转换不改变二进制位，只改变解释方式

6. 溢出与回绕

• 有符号溢出：结果超出表示范围，行为未定义（UB）
• 无符号回绕：结果超出范围时自动模2^n
  • 例如8位无符号：200 + 100 = 300 > 255 → 300 % 256 = 44

1.2 位宽与取值范围

1.2 位宽与取值范围

数据类型	位宽	有符号范围	无符号范围
char	8位	-128 ~ 127	0 ~ 255
short	16位	-32768 ~ 32767	0 ~ 65535
int	32位	-2³¹ ~ 2³¹-1	0 ~ 2³²-1
long long	64位	-2⁶³ ~ 2⁶³-1	0 ~ 2⁶⁴-1

2. 位运算基本操作

2.1 六种基本位运算

// 1. 按位与 &
a & b  // 对应位都为1则为1，否则为0

// 2. 按位或 |
a | b  // 对应位有一个为1则为1

// 3. 按位异或 ^
a ^ b  // 对应位不同则为1，相同则为0

// 4. 按位取反 ~
~a     // 所有位取反（0变1，1变0）

// 5. 左移 <<
a << k // a向左移动k位，低位补0，相当于乘以2^k

// 6. 右移 >>
a >> k // a向右移动k位
       // 对于有符号数，高位补符号位（算术右移）
       // 对于无符号数，高位补0（逻辑右移）

2.2 位运算优先级

从高到低：

1. ~ 按位取反
2. <<, >> 移位运算
3. & 按位与
4. ^ 按位异或
5. | 按位或

重要提醒：位运算优先级低于算术运算，使用时必须加括号！

// 错误示例
if (a & 1 == 0)  // 等价于 a & (1 == 0)，永远为false
// 正确写法
if ((a & 1) == 0)

3. 常用位运算技巧

3.1 获取特定位

// 获取第k位（从0开始，最低位为第0位）
int get_bit(int x, int k) {
    return (x >> k) & 1;
}

// 设置第k位为1
int set_bit(int x, int k) {
    return x | (1 << k);
}

// 设置第k位为0
int clear_bit(int x, int k) {
    return x & ~(1 << k);
}

// 翻转第k位（0变1，1变0）
int flip_bit(int x, int k) {
    return x ^ (1 << k);
}

3.2 lowbit操作

定义：lowbit(x) 返回x的二进制表示中最低位的1所对应的值

int lowbit(int x) {
    return x & -x;
}

原理：在计算机中，负数使用补码表示，-x = ~x + 1

• 例如：x = 1010 1000
  • ~x = 0101 0111
  • ~x + 1 = 0101 1000
  • x & -x = 0000 1000

应用：

1. 统计二进制中1的个数
2. 树状数组（Binary Indexed Tree）核心操作

3.3 统计二进制中1的个数

// 方法1：逐位统计 O(k)，k为位数
int count_bits1(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

// 方法2：lowbit优化 O(m)，m为1的个数
int count_bits2(int x) {
    int cnt = 0;
    while (x) {
        x -= lowbit(x);  // 每次去掉最低位的1
        cnt++;
    }
    return cnt;
}

3.4 判断奇偶性

// 使用位运算判断奇偶性（比取模快）
bool is_odd(int x) {
    return x & 1;  // 奇数返回true
}

bool is_even(int x) {
    return !(x & 1);  // 偶数返回true
}

3.5 乘除2的幂次

// 乘以2^k
int multiply_pow2(int x, int k) {
    return x << k;
}

// 除以2^k（向下取整）
int divide_pow2(int x, int k) {
    return x >> k;
}

// 判断是否为2的幂次
bool is_power_of_two(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

4. 状态压缩

4.1 基本概念

状态压缩是用一个整数的二进制位来表示一个集合的状态，常用于：

• 子集枚举
• 动态规划状态表示（如旅行商问题TSP）
• 棋盘状态表示（如八皇后、数独）

4.2 集合表示

// 用二进制位表示集合，第i位为1表示元素i在集合中
int S = 0;  // 空集

// 添加元素i到集合
S |= (1 << i);

// 从集合中删除元素i
S &= ~(1 << i);

// 判断元素i是否在集合中
bool in_set = (S >> i) & 1;

// 集合大小（元素个数）
int count_bits(int x) {
    int cnt = 0;
    while (x) {
        x -= lowbit(x);  // 每次去掉最低位的1
        cnt++;
    }
    return cnt;
}
int size = count_bits(S);

// 遍历集合中的所有元素
for (int i = 0; i < n; i++) {
    if (S >> i & 1) {
        // 处理元素i
    }
}

// 遍历集合S的所有子集（重要技巧）
for (int sub = S; sub; sub = (sub - 1) & S) {
    // 处理子集sub
}
// 包含空集的情况
int sub = S;
do {
    // 处理子集sub
} while (sub = (sub - 1) & S);

4.3 常见状态压缩操作

// 两个集合的并集
int union_set(int A, int B) {
    return A | B;
}

// 两个集合的交集
int intersection_set(int A, int B) {
    return A & B;
}

// 集合A减去集合B
int difference_set(int A, int B) {
    return A & ~B;
}

// 集合的补集（假设全集为U）
int complement_set(int S, int U) {
    return U ^ S;  // 等价于 ~S & U
}

5. 位运算优化技巧

5.1 交换两个数（不使用临时变量）

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}
// 原理：a ^ b ^ b = a, a ^ b ^ a = b

5.2 绝对值计算

int abs_int(int x) {
    int mask = x >> 31;  // 如果x为负，mask = -1（全1）；否则mask = 0
    return (x ^ mask) - mask;
}
// 等价于：x >= 0 ? x : -x

5.3 判断符号是否相同

bool same_sign(int a, int b) {
    return (a ^ b) >= 0;  // 最高位相同则结果为非负
}

5.4 取模运算优化（对2的幂次取模）

int mod_pow2(int x, int mod) {
    return x & (mod - 1);  // mod必须是2的幂次
}
// 例如：x % 8 等价于 x & 7

三、典型例题精讲

例题1：a^b（快速幂）

题目描述：求 a 的 b 次方对 p 取模的值，其中 1 ≤ a,b,p ≤ 10^9

输入格式：三个整数 a,b,p 输出格式：输出一个整数，表示 a^b mod p 的值

解题思路：

1. 朴素方法：循环b次乘法，时间复杂度O(b)，对于b=10^9会超时
2. 快速幂算法：利用二进制分解指数，时间复杂度O(log b)

算法原理： 将指数b表示为二进制形式：$b = 2^{k} + 2^{k-1} + ... + 2^{0}$ 则 $a^b = a^{2^{k}} × a^{2^{k-1}} × ... × a^{2^{0}}$

在计算过程中维护当前基数 $base = a^{2^k}$，每次指数右移一位时，$base$平方一次

计算过程示例：计算 3^13 mod 7

1. 13的二进制：1101 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1
2. 3^13 = 3^8 × 3^4 × 3^1
3. 计算过程：
   • 初始：res=1, base=3, b=13
   • b=13(奇数)：res=1×3=3, base=3×3=9, b=6
   • b=6(偶数)：base=9×9=81≡4 mod 7, b=3
   • b=3(奇数)：res=3×4=12≡5 mod 7, base=4×4=16≡2 mod 7, b=1
   • b=1(奇数)：res=5×2=10≡3 mod 7, base=2×2=4 mod 7, b=0
4. 结果：3

代码实现：

#include <iostream>
using namespace std;

typedef long long LL;

// 快速幂模板
LL qmi(LL a, LL b, LL p) {
    LL res = 1 % p;  // 处理p=1的情况
    while (b) {
        if (b & 1) res = res * a % p;  // 当前二进制位为1，乘上对应的a^{2^k}
        a = a * a % p;                 // 基数平方
        b >>= 1;                       // 指数右移一位
    }
    return res;
}

int main() {
    LL a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
    return 0;
}

时间复杂度：O(log b) 空间复杂度：O(1)

关键点：

1. 使用long long防止中间结果溢出
2. 初始res = 1 % p处理p=1的情况
3. 每次乘法后立即取模，防止溢出

例题2：64位整数乘法（龟速乘）

题目描述：求 a 乘 b 对 p 取模的值，其中 1 ≤ a,b,p ≤ 10^18

输入格式：三个整数 a,b,p 输出格式：输出一个整数，表示 a×b mod p 的值

问题分析：

• a,b,p最大可达$10^{18}$，直接计算$a×b$可能溢出64位整数范围（约9.22×10^18）
• 需要一种方法在不溢出的情况下计算大数乘法取模

解题思路：

1. 龟速乘（二进制分解法）：类似快速幂的思想，将乘法转化为加法
2. 原理：a×b = a×(b的二进制分解) = $Σ a×2^k$ (b的第k位为1时)

算法步骤：

1. 初始化res=0
2. 当b>0时循环：
   • 如果b的当前最低位为1，则res = (res + a) % p
   • a = (a + a) % p （相当于a×2）
   • b >>= 1
3. 返回res

计算过程示例：计算 7×13 mod 10

1. 13的二进制：1101
2. 计算过程：
   • 初始：res=0, a=7, b=13
   • b=13(奇数)：res=0+7=7, a=7+7=14≡4, b=6
   • b=6(偶数)：a=4+4=8, b=3
   • b=3(奇数)：res=7+8=15≡5, a=8+8=16≡6, b=1
   • b=1(奇数)：res=5+6=11≡1, a=6+6=12≡2, b=0
3. 结果：1 (7×13=91, 91 mod 10 = 1)

代码实现：

#include <iostream>
using namespace std;

typedef long long LL;

// 龟速乘模板
LL qmul(LL a, LL b, LL p) {
    LL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;  // 当前位为1，加上对应的a×2^k
        a = (a + a) % p;                 // a翻倍，相当于a×2
        b >>= 1;                         // b右移一位
    }
    return res;
}

int main() {
    LL a, b, p;
    cin >> a >> b >> p;
    cout << qmul(a, b, p) << endl;
    return 0;
}

时间复杂度：O(log b) 空间复杂度：O(1)

其他方法：

1. long double法：

   LL qmul(LL a, LL b, LL p) {
       LL c = (long double)a * b / p;
       LL res = a * b - c * p;
       if (res < 0) res += p;
       else if (res >= p) res -= p;
       return res;
   }
   

例题3：起床困难综合征

题目描述：有n扇门，每扇门有一个操作(AND, OR, XOR)和一个数值t。初始攻击力为[0,m]之间的一个整数，需要依次通过所有门，求最终攻击力的最大值。

输入格式：

• 第一行：n m
• 接下来n行：每行一个操作符和一个数t
  • AND x
  • OR x
  • XOR x

输出格式：一个整数，表示最大攻击力

问题分析：

1. 位运算的独立性：不同二进制位之间互不影响
2. 可以逐位考虑，确定每一位选择0还是1能得到最大结果
3. 需要在[0,m]范围内选择初始值

解题思路：

1. 位独立性：由于AND、OR、XOR都是按位操作，每一位的结果只取决于该位的初始值
2. 贪心策略：从高位到低位依次确定
   • 优先让高位为1（如果可能）
   • 当前位选1需要满足：当前位选1后初始值不超过m
   • 当前位选1能增加最终结果
3. 预处理：对于每一位，分别计算初始为0和初始为1时的最终结果

算法步骤：

1. 设初始值val=0，结果ans=0
2. 从高位到低位（29位到0位，因为$m≤10^9≈2^{30}$）：
   • 计算如果该位初始为0，经过所有门后的结果res0
   • 计算如果该位初始为1，经过所有门后的结果res1
   • 如果val + (1<<k) ≤ m 且 res1 > res0：
     • 该位选1更优，val += 1<<k，ans += res1<<k
   • 否则：
     • 该位选0，ans += res0<<k

代码实现：

#include <iostream>
#include <string>
using namespace std;

typedef pair<string, int> PSI;

const int N = 100010;
PSI doors[N];
int n, m;

// 计算某一位初始为x时经过所有门的结果
int calc(int bit, int x) {
    for (int i = 0; i < n; i++) {
        string op = doors[i].first;
        int t = (doors[i].second >> bit) & 1;  // 取第bit位

        if (op == "AND") x &= t;
        else if (op == "OR") x |= t;
        else x ^= t;
    }
    return x;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> doors[i].first >> doors[i].second;
    }

    int val = 0;  // 当前选择的初始值
    int ans = 0;  // 最终结果

    // 从高位到低位贪心
    for (int bit = 29; bit >= 0; bit--) {
        int res0 = calc(bit, 0);  // 该位初始为0的结果
        int res1 = calc(bit, 1);  // 该位初始为1的结果

        // 如果该位选1不超过m，且选1结果更优
        if (val + (1 << bit) <= m && res1 > res0) {
            val += (1 << bit);
            ans += (res1 << bit);
        } else {
            ans += (res0 << bit);
        }
    }

    cout << ans << endl;
    return 0;
}

时间复杂度：O(n log m)，其中log m约30 空间复杂度：O(n)

四、总结

基础训练（必须掌握）

1. 实现所有位运算基本操作（get_bit, set_bit, clear_bit, flip_bit）
2. 实现lowbit函数并理解其原理
3. 实现统计二进制中1的个数的方法
4. 实现集合的基本操作（并、交、差、补）
5. 理解状态压缩的概念
6. 实现a^b，64位整数乘法，起床困难综合征

拓展训练

1. 解决位运算相关的数学问题
2. 学习使用bitset类（C++ STL）自行查阅资料。

六、常见错误与调试技巧

常见错误

1. 优先级错误：忘记加括号 if (a & 1 == 0)
2. 符号位问题：右移有符号负数时高位补1
3. 溢出问题：左移导致符号位改变
4. 位宽问题：对不同类型进行位运算
5. 越界访问：访问超过类型位数的位

调试技巧

1. 二进制打印：调试时打印变量的二进制表示

void print_binary(int x) {
    for (int i = 31; i >= 0; i--) {
        cout << ((x >> i) & 1);
        if (i % 8 == 0) cout << " ";
    }
    cout << endl;
}

2. 边界测试：测试0、-1、INT_MAX、INT_MIN等边界情况
3. 小数据验证：使用小数据手动计算验证
4. 对比验证：对比暴力算法与位运算算法的结果

参考书籍 《算法竞赛进阶指南》第一章 0x01节