Less is more.

外观

0.0 基本算法--位运算

2772字约9分钟

2024-11-03

《算法竞赛进阶指南/李煜东》0x00 章节基本算法——位运算。

本节知识点：补码、移位运算、二进制状态压缩、lowbit 运算。

位运算

bit 是度量信息的单位，包含 0 和 1 两种状态。计算机的各种运算最后无不归结为一个个 bit 的变化。熟练掌握并利用位运算，能够帮助我们理解程序运行中的种种表现，提高程序运行的时空效率，降低编程复杂度。

在 m 位二进制数中，为方便起见，通常称最低位为第 0 位，从右到左依此类推，最高位为第 m-1 位。本书默认使用这种表示方法来指明二进制数以及整数在二进制表示下的位数。

补码

::: int != i32；uint != u32

在信息学竞赛中，我们一般认为int即为32位有符号整数，unsigned int即为32位无符号整数。在大多数现代计算机上也确实如此。不过，在C++标准中，仅规定了int和unsigned int的位数不小于16。直接把int和unsigned int与32位整数画等号实际上是不严谨的。

:::

  • 32 位无符号整数：直接看做 32 位二进制数 N
  • 32 位有符号整数：最高位为符号为，0 表示非负数，1 表示负数。非负数直接表示，负数为 -(~S + 1)

补码也被称为“二补数”，“一补数”是反码。补码具有自然溢出取模、0 编码唯一性、能表示多一个数的优点。

因为二进制表示 int 需要写出 32 位，因此为了直观体现出每一个位，所以用十六进制表示一个常数，0x<...>。0x3F 3F 3F 3F 是一个很有用的 值，它是满足以下两个条件的最大整数：

  • 整数的两倍不超过 0x7F FF FF FF（int 能表示的最大正整数）
  • 整数的每 8 位（每字节）都是相同的。

程序设计中经常需要使用 memset(a, val, sizeof(a)) 来初始化一个 int 数组 a，因此 0x7F 7F 7F 7F 是该语句能够初始化的最大值。当需要把一个数组中的数值初始化成正无穷时，为了避免加法算数上溢和繁琐判断，经常使用 memset(a, 0x3f, sizeof(a)) 给数组赋值 0x3F 3F 3F 3F 来替代。

移位运算

  • 左移：二进制数字向左移动，高位越界舍弃，低位补 0。

    • 1<<n=2n1 << n = 2^n
    • n<<1=2nn << 1 = 2n

  • 算术右移：二进制数字向右移动，高位符号位填充，低位越界舍弃。

    n>>1=⌊n2.0⌋n >> 1= \lfloor \frac{n}{2.0} \rfloor 算术右移等于除以 2 向下取整，而 “整数/2” 在 C++ 的实现是 “除以 2 向零取整”。

  • 逻辑右移：二进制补码表示下把数字向右移动，高位补 0，低位舍弃。

C++ 语法没有规定右移的实现方式，取决于编译器。一般编译器使用算术右移。

一些模数的性质：

若 amod  p=bmod  pa \mod p =b \mod p，那么 a≡b (mod  p)a \equiv b\ (\mod p)

对于 a≡b,c≡da \equiv b,c\equiv d，有（均 mod  p\mod p）

a+c≡b+da + c \equiv b +d

a−c≡b−da - c \equiv b -d

a−c≡b−da - c \equiv b -d

即，对于求加、减、乘的模数，先模再运算是一样的（除法没有）。

abmod  p=(a⋅bp−2)mod  p\frac{a}{b}\mod p=(a·b^{p-2})\mod p

即在代码中的模处理[1]

MOD = 1_000_000_007

// 加
(a + b) % MOD

// 减
(a - b + MOD) % MOD

// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
(a % MOD + MOD) % MOD

// 乘（注意使用 64 位整数）
a * b % MOD

// 多个数相乘，要步步取模，防止溢出
a * b % MOD * c % MOD

// 除（MOD 是质数且 b 不是 MOD 的倍数）
a * qpow(b, MOD - 2, MOD) % MOD
【POJ1995】a^b

【POJ1995】求 a 的 b 次方对 p 取模的值，其中 1≤a,b,p≤1091 \le a,b,p \le 10^9

快速幂乘。

令 b=ck−12k−1+ck−22k−2+...+c020b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_02^0 ，ckc_k 即是 b 的二进制表示

那么 ab=ack−12k−1ack−22k−2...ac020a^b=a^{c_{k-1}2^{k-1}}a^{c_{k-2}2^{k-2}}...a^{c_02^0}

注意到 a2k=a2⋅2k−1=(a2k−1)2a^{2^{k}}=a^{2·2^{k-1}}=(a^{2^{k-1}})^2，可以递推

那么 aba^b 则是由每一项次 a2ka^{2^k} 累乘而来的，那么可以根据 ckc_k 的值选择。

int power(int a, int b, int p) { // (a ^ b) mod p
  int ans = 1 % p;
  for ( ; b; b >>= 1) {
    if (b & 0x1) ans = ((long long)ans * b) % p;
    a = ((long long)a * b) % p;
  }
  return ans;
}

注意到 a, b 为 int，相乘可能会溢出，所以需要强转成 long long 计算。

但是当 a, b 为 long long 时，此时没有更大的类型（其实也有 😁，__int128）可以容纳乘积怎么办？

64 位整数乘法

求 (a×b)mod  p, 1≤a,b,p≤1018(a \times b) \mod {p},\ 1\le a,b,p \le 10^{18}

;;;ch02 类似快速幂乘

令 b=ck−12k−1+ck−22k−2+...+c020b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_02^0 ，ckc_k 即是 b 的二进制表示

那么 a⋅b=ack−12k−1+ack−22k−2+...+ac020a·b=ac_{k-1}2^{k-1}+ac_{k-2}2^{k-2}+...+ac_02^0

那么有 a⋅2k=2(a⋅2k−1)a·2^{k}=2(a·2^{k-1}) 为递推式，

结果为递推式的累加。

long long mul(long long a, long long b, long long p) {
  long long ans = 0;
  for ( ; b; b >>= 1) {
    if (b & 0x1) ans += a;
    a = (a * 2) % p;
  }
  return ans;
}

;;;

;;;ch02 O1 快速乘

由模数的定义可知，a∗bmod  p=a∗b−⌊a∗b/p⌋∗pa*b\mod p = a*b-\lfloor{a*b/p}\rfloor * p，虽然前后都可能爆 ll，但是差值确不会。非常玄学的方法呢！

long long mul(long long a, long long b, long long p) {
  a %= p, b %= p;
  long long c = (long double)a * b / p;
  long long ans = a * b - c * p;
  if (ans < 0) ans += p;
  else if (ans >= p) ans -= p;
  return ans;
}

;;;

二进制状态压缩

二进制状态压缩，是指将一个长度为 m 的 bool 数组使用一个 m 位二进制整数表示并存储的方法。

操作运算
整数 n 的第 k 位(n>>k)&1
整数 n 的后 k 位n&((1<<k)-1)
整数 n 的第 k 位取反n^(1<<k)
整数 n 的第 k 位赋值 1`n
整数 n 的第 k 位赋值 0n&(~(1<<k))

这种方法运算简便并且节省了程序运行的时间空间，当 m 不大时可用一个整数类型存储，当 m 较大时，可以使用整数数组，也可以直接利用 C++ STL 提供的 bitset 实现。

最短 Hamilton 路径

最短 Hamilton 路径[2]：给定一张 n(n≤20)n(n\le 20) 个点的带权无向图，点从 0～n−10～n-1 标号，求起点 0 到终点 n−1n-1 的最短的 Hamilton 路径。Hamilton 路径的定义是从 0 到 n−1n-1 不重不漏地经过每个点恰好一次。

  1. 朴素做法，即枚举 n 个点的全排列，计算路径长度的最小值，总共需要 O(n∗n!)O(n*n!) 的复杂度；

  2. 二进制状态压缩 DP：

    利用一个 n 位二进制数，通过 n 的第 i 位表示点经过的状态。

    利用 F(i,j)F(i,j) 来表示状态，i 为已经过的点的位图，j 为目前正在的点。

    那么有转移方程 F(i,j)=min⁡{ F[i⊕(1<<j),k]+weight(k,j) }F(i,j)=\min{\set{F[i \oplus (1<<j),k]+weight(k,j)}} 其中 kk 为已经经历的点。

    #include <iostream>
#include <cstring>

using namespace std;

int main() {
    int weight[20][20];
    int N = 0;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> weight[i][j];
        }
    }
    
    int dp[1<<20][20];
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0; // 初始状态：经过了 0 当前为 0
    for (int i = 1; i < 1<<N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!((i >> j) & 1)) continue;
            for (int k = 0; k < N; ++k) {
                if ((i & (1 << k)) == 0) continue;
                dp[i][j] = min(dp[i^(1<<j)][k] + weight[j][k], dp[i][j]);
            }
        }
    }
    cout << dp[(1<<N)-1][N-1];
}
起床困难综合症

AcWing'998[3]：求一个在区间 [0,m][0,m] 的数，在经过了 nn 组 (opi,ti)(op_i,t_i) 的运算后能够取得最大值 result，其中 opi∈{ OR,XOR,AND }op_i\in\set{OR,XOR,AND}。数值 n≤105,m,ti≤109n \le10^5,m,t_i\le10^9。

解法：位运算二进制不进位，故这个数的每一个位都是独立的，要想结果最大化即要让结果的高位尽可能为 1 且原始数不能超过 mm。

#include <cstdio>
#include <iostream>

using namespace std;

pair<string, int> a[100005];
int m, n;
int calc(int bit, int now) {
  for (int i = 0; i < n; ++i) {
    int x = a[i].second >> bit & 1;
    if (a[i].first == "AND") {
        now &= x;
    } else if (a[i].first == "OR"){
        now |= x;
    } else if (a[i].first == "XOR") {
        now ^= x;
    }
  }
  return now;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    char op[5]; int x;
    scanf("%s%d", op, &x);
    a[i] = make_pair(op, x);
  }
  int val = 0, ans = 0;
  for (int bit = 29; bit >= 0; --bit) {
    int ans1 = calc(bit, 1), ans0 = calc(bit, 0);
    if ((val | (1<<bit)) <= m && ans1 > ans0) {
      val |= (1<<bit);
      ans |= (ans1<<bit);
    } else {
      ans |= (ans0<<bit);
    }
  }
  cout << ans << endl;
}

成对变换

对于非负整数 n：

  • 当 n 为偶数时，n xor 1 等于 n + 1
  • 当 n 为奇数时，n xor 1 等于 n - 1

因此，“0，1” “2，3” “4， 5” 关于 xor 1 运算构成成对变换。这一性质经常用于图论中邻接表中边集的存储，通过 xor 1 运算获取与当前边 (x,y) 反向的边 (y,x) 的存储位置。

lowbit 运算

lowbit(n)lowbit(n) 定义为非负整数 n 在二进制表示下 “最低位的 1 以及后边所有的 0” 构成的数值。

::: lowbit(n)=n&(~n+1)=n&(-n)

~n + 1 与 n 的区别为，高于最低位的 1 的位数全为取反，最低位的 1 为 1，低于这个位数的全为 0，故 n & (~n+1) 就是 lowbit，另外 ~n+1 实则 -n 的补码表示。

:::

::: lowbit 操作配合哈希表可以用来找出整数二进制下所有是 1 的位

;;;id1 朴素版本

对数的位数进行预处理，令 H[1<<i] = i，此时如果 N 在 20 位以内，则需要大小为 (1<<N) + 1 的哈希表。

const MAX_N = 1 << 20;
int H[MAX_N+1];
for (int i = 0; i <= 20; i++) H[1 << i] = i;
while (cin >> n) {
  while (n > 0) {
    cout << H[n&-n] << ' ';
  	n -= n&-n;
  }
  cout << endl;
}

;;;

;;;id1 优化版本

朴素版本虽然只记录了 21 个映射关系，但却需要一个 (1<<20)+1 大小的哈希表。利用 ∀k∈[0,35],2kmod  37\forall k \in [0,35],2^k \mod 37 互不相等，且恰好取遍整数 1-36，即集合的一一对应关系，可以压缩哈希表的大小。

int H[37];
for (int i = 0; i <= 36; i++) H[(1ll << i) % 37] = i;
while (cin >> n) {
  while (n > 0) {
    cout << H[(n&-n) % 37] << ' ';
  	n -= n&-n;
  }
  cout << endl;
}

;;;

:::

另外，lowbit 运算也是树状数组（0x42节）的一个基本运算。

GCC 编译器还提供了一些内置函数可以高效计算 lowbit 以及二进制数中 1 的个数，不过这些函数并非 C 标准，尽量不要随意使用。

int __builtin_ctz(unsigned int x);
int __builtin_ctzll(unsigned long long x);
// 返回 x 的二进制表示下最低位的 1 后面有多少个 0
int __builtin_popcount(unsigned int x);
int __builtin_popcountll(unsigned long long x);
// 返回 x 的二进制表示下有多少位为 1

  1. 分享丨模运算的世界：当加减乘除遇上取模（模运算恒等式/费马小定理）https://leetcode.cn/circle/discuss/mDfnkW/ ↩︎

  2. 最短Hamilton路径 https://www.acwing.com/file_system/file/content/whole/index/content/3642/ ↩︎

  3. 起床困难综合症 https://www.acwing.com/problem/content/1000/ ↩︎