位运算

· · 算法·理论

位运算

想要更丰富的视觉体验？

下载离线版本 html版文档 用浏览器打开即可

与、或、异或

同属双目运算

将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

运算 运算符 数学符号表示 解释
与 & \&、\operatorname{and} 只有两个对应位都为 1 时才为 1
或 \| \mid、\operatorname{or} 只要两个对应位中有一个 1 时就为 1
异或 ~ ^ ~ \oplus、\operatorname{xor} 只有两个对应位不同时才为 1

注意区分逻辑与（对应的数学符号为 \wedge）和按位与、逻辑或（\vee）和按位或的区别。

异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 a \oplus b \oplus b = a 。 根据该性质，可以使用前缀和来快速查询区间异或值。

举例：

\begin{aligned} 5 &=(101)_2\\ 6 &=(110)_2\\ 5\: \& \: 6 &=(100)_2 =\ 4\\ 5\: |\: 6 &=(111)_2 =\ 7\\ 5\oplus6 &=(011)_2 =\ 3\\ \end{aligned}

取反

取反是对一个数 num 进行的位运算，即单目运算。

其对应的运算符为 ~。它的作用是把 num 的二进制补码中的 0 和 1 全部取反（0 变为 1，1 变为 0）。有符号整数的符号位在 ~ 运算中同样会取反。

补码：在二进制表示下，正数和 0 的补码为其本身，负数的补码是将其对应正数按位取反后加一。

举例（有符号整数）：

\begin{aligned} 5&=(00000101)_2\\ \sim 5 &= (11111010)_2=-6\\ -5\text{ 的补码}&=(11111011)_2\\ \sim (-5)&=(00000100)_2=4 \end{aligned}

补码的本质是让加法运算替换减法运算，所以负数的补码加上其对应的正整数要等于 0。

左移和右移

num << i 表示将 num 的二进制表示向左移动 i 位所得的值。

num >> i 表示将 num 的二进制表示向右移动 i 位所得的值。

举例：

\begin{aligned} 11&=(00001011)_2\\ 11<<3&=(01011000)_2=88\\ 11>>2&=(00000010)_2=2 \end{aligned}

移位运算中如果出现如下情况，则其行为未定义：

  1. 右操作数（即移位数）为负值；
  2. 右操作数大于等于左操作数的位数；

例如，对于 int 类型的变量 a ， a<<-1 和 a<<32 都是未定义的。

对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。[^note1]对一个负数执行左移操作也未定义。[^note2]

对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 0；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 0，负数为 1）补齐。[^note3]

复合赋值位运算符

和 += , -= 等运算符类似，位运算也有复合赋值运算符： &= , |= , ^= , <<= , >>= 。（取反是单目运算，所以没有。）

关于优先级

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以使用时需多加注意，在必要时添加括号。

位运算的应用

位运算一般有三种作用：

  1. 高效地进行某些运算，代替其它低效的方式。

  2. 表示集合（常用于 状压 DP）。

  3. 题目本来就要求进行位运算。

需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但是位移操作可以快速计算关于2的幂次运算） 在竞赛中，位运算优化一般不会决定复杂度的上界。

有关 2 的幂的应用

由于位运算针对的是变量的二进制位，因此可以推广出许多与 2 的整数次幂有关的应用。

将一个数乘（除） 2 的非负整数次幂：

int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
 }
 int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
    return n >> m;
  }

!!! warning 我们平常写的除法是向 0 取整，而这里的右移是向下取整，即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别，如： -1 / 2 的值为 0 ，而 -1 >> 1 的值为 -1 。

取绝对值

int Abs(int n) {
    return (n ^ (n >> 31)) - (n >> 31);
    /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31  等于
    -1 若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1) 需要计算 n 和 -1
    的补码，然后进行异或运算， 结果 n 变号并且为 n 的绝对值减 1，再减去 -1
    就是绝对值 */
}

取两个数的最大/最小值

// 如果 a >= b, (a - b) >> 31 为 0，否则为 -1
int max(int a, int b) {
    return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
}
int min(int a, int b) {
    return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31));
}

操作一个数的二进制位

// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) {
    return (a >> b) & 1;
}

将一个数二进制的某一位设置为 0：

    // 将 a 的第 b 位设置为 0 ，最低位编号为 0
    int unsetBit(int a, int b) { return a & ~(1 << b); }

将一个数二进制的某一位设置为 1：

     // 将 a 的第 b 位设置为 1 ，最低位编号为 0
    int setBit(int a, int b) { return a | (1 << b); }

将一个数二进制的某一位取反：

    // 将 a 的第 b 位取反 ，最低位编号为 0
    int flapBit(int a, int b) { return a ^ (1 << b); }

这些操作相当于将一个 32 位整型变量当作一个长度为 32 的 bool 数组,可以使用 bitset 实现共多功能。

内建函数

GCC 中还有一些用于位运算的内建函数：

  1. int __builtin_ffs(int x) ：返回 x 的二进制末尾最后一个 1 的位置，位置的编号从 1 开始（最低位编号为 1 ）。当 x 为 0 时返回 0 。

  2. int __builtin_clz(unsigned int x) ：返回 x 的二进制的前导 0 的个数。当 x 为 0 时，结果未定义。

  3. int __builtin_ctz(unsigned int x) ：返回 x 的二进制末尾连续 0 的个数。当 x 为 0 时，结果未定义。

  4. int __builtin_clrsb(int x) ：当 x 的符号位为 0 时返回 x 的二进制的前导 0 的个数减一，否则返回 x 的二进制的前导 1 的个数减一。

  5. int __builtin_popcount(unsigned int x) ：返回 x 的二进制中 1 的个数。

  6. int __builtin_parity(unsigned int x) ：判断 x 的二进制中 1 的个数的奇偶性。

这些函数都可以在函数名末尾添加 l 或 ll （如 __builtin_popcountll ）来使参数类型变为 ( unsigned ) long 或 ( unsigned ) long long （返回值仍然是 int 类型）。 例如，我们有时候希望求出一个数以二为底的对数，如果不考虑 0 的特殊情况，就相当于这个数二进制的位数 -1 ，而一个数 n 的二进制表示的位数可以使用 32-__builtin_clz(n) 表示，因此 31-__builtin_clz(n) 就可以求出 n 以二为底的对数。

内建函数由汇编指令构成，速度非常快。

更多位数

如果需要操作的集合非常大，可以使用 bitset。

STL - bitset

1) 头文件 #include <bitset> 2) 定义 bitset<n> ibs; 表示一个 n 位的二进制数，< >中填写位数。

3) 运算符 ~ibs 返回对 ibs 每一位取反后的结果。 & | ^ 返回对两个位数相同的 bitset 执行按位与、或、异或运算的结果。 << >> 返回把一个 bitset 左移、右移若干位的结果。 == != 比较两个位数相同的 bitset 代表的二进制数是否完全相等。

4) 位的存储/访问 ibs[k] 表示 ibs 的第 k 位，既可取值也可赋值 ibs.count() 返回二进制串中有多少个 1. ibs.any() 全为 0 返回 false 存在一位及以上 1 返回 true. ibs.none() 全为 0 返回 true 存在一位及以上 1 返回 false.

5) 位的操作 ibs.set(k, v) 将 ibs 的第 k 位改为 v 即 ibs[k] = v 不填参数则将 ibs 所有位赋为 0. ibs.reset(k) 把 ibs 的第 k 位改为 0 即 ibs[k] = v. 不填参数则将 ibs 所有位赋为 0. ibs.flip(k) 把 ibs 的第 k 位取反。 不填参数则将 ibs 所有位取反。

6) Bitset的操作 ibs.to_string() 返回 string 类型的 ibs. ibs.to_ulong() 返回 unsinged long int 类型的 ibs(十进制). ibs.to_ullong() 返回 unsinged long long类型的 ibs(十进制).

题目推荐

洛谷 P1100 高低位交换 洛谷 P1161 开灯 洛谷 P1225 黑白棋游戏

参考资料与注释

  1. 位运算技巧： https://graphics.stanford.edu/~seander/bithacks.html
  2. Other Builtins of GCC： https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

[^note1]: 适用于 C++14 以前的标准。在 C++14 和 C++17 标准中，若原值为带符号类型，且移位后的结果能被原类型的无符号版本容纳，则将该结果 转换 为相应的带符号值，否则行为未定义。在 C++20 标准中，规定了无论是带符号数还是无符号数，左移均直接舍弃移出结果类型的位。

[^note2]: 适用于 C++20 以前的标准。

[^note3]: 这种右移方式称为算术右移。在 C++20 以前的标准中，并没有规定带符号数右移运算的实现方式，大多数平台均采用算术右移。在 C++20 标准中，规定了带符号数右移运算是算术右移。