经典题目
P4085 2 的幂
abc270a A - 1-2-4 Test
abc269c C - Submask
P4086 只出现一次的数字
P266 【例44.1】 输出二进制补码

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共 66 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

为了方便叙述，下文中省略“按位”。

与、或、异或

这三者都是两数间的运算，因此在这里一起讲解。

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

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

注意区分逻辑与（对应的数学符号为 ∧\wedge）和按位与、逻辑或（∨\vee）和按位或的区别。网络中的资料中使用的符号多有不规范之处，以上下文为准。

异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 a⊕b⊕b=aa \oplus b \oplus b = a 。

举例：

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

取反

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

取反暂无默认的数学符号表示，其对应的运算符为 ~。它的作用是把 numnum 的二进制补码中的 00 和 11 全部取反（00 变为 11，11 变为 00）。有符号整数的符号位在 ~ 运算中同样会取反。

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

举例（有符号整数）：

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

左移和右移

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

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

举例：

$$\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 都是未定义的。

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

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

复合赋值位运算符

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

关于优先级

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

原码、反码、补码

1.1 原码的介绍

原码是一种用于表示有符号整数的表示方式。 原码的最高位用来表示符号，0表示正数，1表示负数，而其余位则表示整数的值。 例如，在一个8位的原码中，+3可以表示为 00000011，-3则表示为 10000011。

1.2 原码的表示

  1. 正数的原码反码补码是其本身（三码合一）。 如 7的原码：0000 0111
  2. 负数的原码符号位为1，数值位为其绝对值。 如 -7的原码：1000 0111

若 X = +1110, 则[X]原 = 0,1110 用逗号隔开 符号位和数值位

若 X = -1110, 则[X]原 = 1,1110 用逗号隔开 符号位和数值位

1.3 原码的范围

注：1Byte (字节) = 8 bit (位)

在使用 n 位二进制进行原码表示时，原码的范围可以通过以下方式计算：

如果使用 n 位二进制表示原码，其中最高位为符号位，剩下的 n-1 位为数值位，则原码的范围可以计算如下：

对于有符号的原码表示，最高位为符号位，0 表示正数，1 表示负数。 假设 n 位二进制表示中，最高位为符号位，即第 n 位，则有效的数值位共有 n-1 位。

  • 对于无符号整数，n 位二进制可以表示 2^(n-1) 个不同的数值，其范围从 0 到 2^(n-1)-1。
  • 对于有符号整数，n 位二进制可以表示从 -(2^(n-1)-1) 到 2^(n-1)-1 的范围，其中最高位为符号位。

例如，如果使用 8 位二进制进行原码表示，则有符号整数的范围为 -127 到 127，无符号整数的范围为从 0 到 255。

需要注意的是，由于有一个比特用于表示符号位，因此有符号整数的表示范围比无符号整数小一半。

1.4 原码计算的弊端

  1. 加法和减法不统一：在原码表示中，正数和负数的加法、减法操作需要分别处理。在进行加法运算时，需要考虑符号位，并且可能存在溢出或进位的问题。减法运算也需要额外的步骤来处理负数的减法，使得运算相对复杂。

利用原码进行计算的时候，如果是正数完全没有问题；但是如果是负数计算，结果就出错，实际运算的方向跟正确的运算方向是相反的。

  1. 零的表示不唯一：在原码表示中，零可以有两种表示方式，即正零（0000 0000）和负零（1000 0000）。这样会导致在计算中出现冗余和不一致的情况，增加了处理零的复杂性。
  2. 符号位的处理困难：因为符号位单独存在，并且参与运算，所以在进行运算时需要特殊处理符号位。这不仅使得运算过程更加繁琐，还增加了错误的可能性。
  3. 浪费存储空间：原码表示中，负数的位数较多，会占用更多的存储空间。这样会浪费存储资源，并且增加了数据传输和处理的复杂性。

2 反码

2.1 反码出现的目的

  1. 为了解决原码不能计算负数的问题。
  2. 实现二进制加法：反码的另一个目的是使得二进制加法可以统一进行，无论是正数还是负数。对于使用反码表示的负数，加法运算就变成了非常简单的按位相加操作。这样可以简化计算，减少运算过程中的特殊情况。

2.2 反码的表示

正数的原码反码补码是其本身，**负数的反码是在原码的基础上，符号位不变。数值位取反，0变1，1变0。**有 +0 -0 之分

2.3 反码的弊端

负数运算的时候，如果结果不跨0，是没有任何问题的，但是如果结果跨0，跟实际结果会有1的偏差。

3 补码

计算机中的存储和计算都是以补码的形式进行的。

3.1 补码出现的目的

为了解决负数计算时跨0的问题而出现的。

3.2 补码的表示

正数的原码反码补码是其本身，负数的补码在反码的基础上+1。 另外补码还能多记录一个特殊的值-128，该数据在1个字节下，没有原码和反码。

3.3 补码的优点

唯一的零表示：解决了反码表示中存在的两个零（正零和负零）的问题。

简化运算：补码的加法和减法运算可以通过相同的方式进行，无需额外的特殊处理。这简化了计算机系统中对负数的运算过程。

扩展表示范围：补码能够更有效地表示负数，且不占用额外的位数。它允许使用相同的位数表示更大的数值范围。

位运算的应用

位运算一般有三种作用：

  1. 高效地进行某些运算，代替其它低效的方式。
  2. 表示集合。（常用于 状压 DP 。）
  3. 题目本来就要求进行位运算。

需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像“乘 2 的非负整数次幂”和“除以 2 的非负整数次幂”就最好使用位运算，因为此时使用位运算可以优化复杂度。）

有关 2 的幂的应用

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

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

// C++ Version
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 我们平常写的除法是向 00 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 00 时两种方法等价，当数小于 00 时会有区别，如： -1 / 2 的值为 00 ，而 -1 >> 1 的值为 −1-1 。

取绝对值

在某些机器上，效率比 n > 0 ? n : -n 高。

// C++ Version
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 高。

// C++ Version
// 如果 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); }

判断两非零数符号是否相同

// C++ Version
bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

交换两个数

???+note "该方法具有局限性" 这种方式只能用来交换两个整数，使用范围有限。

对于一般情况下的交换操作，推荐直接调用 `algorithm` 库中的 `std::swap` 函数。

void swap(int &a, int &b) { a ^= b ^= a ^= b; }

操作一个数的二进制位

获取一个数二进制的某一位：

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

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

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

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

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

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

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

这些操作相当于将一个 3232 位整型变量当作一个长度为 3232 的布尔数组。

汉明权重

汉明权重是一串符号中不同于（定义在其所使用的字符集上的）零符号（zero-symbol）的个数。对于一个二进制数，它的汉明权重就等于它 11 的个数（即 popcount）。

求一个数的汉明权重可以循环求解：我们不断地去掉这个数在二进制下的最后一位（即右移 11 位），维护一个答案变量，在除的过程中根据最低位是否为 11 更新答案。

代码如下：

// 求 x 的汉明权重
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

求一个数的汉明权重还可以使用 lowbit 操作：我们将这个数不断地减去它的 lowbit[4]，直到这个数变为 00。

代码如下：

// 求 x 的汉明权重
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x -= x & -x;
    }
    return cnt;
}

构造汉明权重递增的排列

在 状压 DP 中，按照 popcount 递增的顺序枚举有时可以避免重复枚举状态。这是构造汉明权重递增的排列的一大作用。

下面我们来具体探究如何在 O(n)O(n) 时间内构造汉明权重递增的排列。

我们知道，一个汉明权重为 nn 的最小的整数为 2n−12^n-1。只要可以在常数时间构造出一个整数汉明权重相等的后继，我们就可以通过枚举汉明权重，从 2n−12^n-1 开始不断寻找下一个数的方式，在 O(n)O(n) 时间内构造出 0∼n0\sim n 的符合要求的排列。

而找出一个数 xx 汉明权重相等的后继有这样的思路，以 (10110)2(10110)_2 为例：

  • 把 (10110)2(10110)_2 最右边的 11 向左移动，如果不能移动，移动它左边的 11，以此类推，得到 (11010)2(11010)_2。
  • 把得到的 (11010)2(11010)_2 最后移动的 11 原先的位置一直到最低位的所有 11 都移到最右边。这里最后移动的 11 原来在第三位，所以最后三位 010010 要变成 001001，得到 (11001)2(11001)_2。

这个过程可以用位运算优化：

int t = x + (x & -x);
x = t | ((((t&-t)/(x&-x))>>1)-1);
  • 第一个步骤中，我们把数 xx 加上它的 lowbit，在二进制表示下，就相当于把 xx 最右边的连续一段 11 换成它左边的一个 11。如刚才提到的二进制数 (10110)2(10110)_2，它在加上它的 lowbit 后是 (11000)2(11000)_2。这其实得到了我们答案的前半部分。
  • 我们接下来要把答案后面的 11 补齐，tt 的 lowbit 是 xx 最右边连续一段 11 最左边的 11 移动后的位置，而 xx 的 lowbit 则是 xx 最右边连续一段 11 最左边的位置。还是以 (10110)2(10110)_2 为例，t=(11000)2t = (11000)_2，lowbit⁡(t)=(01000)2\operatorname{lowbit}(t) = (01000)_2，lowbit⁡(x)=(00010)2\operatorname{lowbit}(x)=(00010)_2。
  • 接下来的除法操作是这种位运算中最难理解的部分，但也是最关键的部分。我们设原数最右边连续一段 11 最高位的 11 在第 rr 位上（位数从 00 开始），最低位的 11 在第 ll 位，tt 的 lowbit 等于 1 << (r+1) ，xx 的 lowbit 等于 1 << l， (((t&-t)/(x&-x))>>1) 得到的，就是 (1<<(r+1))/(1<<l)/2 = (1<<r)/(1<<l) = 1<<(r-l) ，在二进制表示下就是 11 后面跟上 r−lr-l 个零，零的个数正好等于连续 11 的个数减去 11 。举我们刚才的数为例，$\frac{\operatorname{lowbit(t)\div 2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2$ 。把这个数减去 11 得到的就是我们要补全的低位，或上原来的数就可以得到答案。

所以枚举 0∼n0\sim n 按汉明权重递增的排列的完整代码为：

for (int i = 0; (1<<i)-1 <= n; i++) {
    for (int x = (1<<i)-1, t; x <= n; t = x+(x&-x), x = x ? (t|((((t&-t)/(x&-x))>>1)-1)) : (n+1)) {
        // 写下需要完成的操作
    }
}

其中要注意 00 的特判，因为 00 没有相同汉明权重的后继。

内建函数

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

  1. int __builtin_ffs(int x) ：返回 xx 的二进制末尾最后一个 11 的位置，位置的编号从 11 开始（最低位编号为 11 ）。当 xx 为 00 时返回 00 。
  2. int __builtin_clz(unsigned int x) ：返回 xx 的二进制的前导 00 的个数。当 xx 为 00 时，结果未定义。
  3. int __builtin_ctz(unsigned int x) ：返回 xx 的二进制末尾连续 00 的个数。当 xx 为 00 时，结果未定义。
  4. int __builtin_clrsb(int x) ：当 xx 的符号位为 00 时返回 xx 的二进制的前导 00 的个数减一，否则返回 xx 的二进制的前导 11 的个数减一。
  5. int __builtin_popcount(unsigned int x) ：返回 xx 的二进制中 11 的个数。
  6. int __builtin_parity(unsigned int x) ：判断 xx 的二进制中 11 的个数的奇偶性。

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

由于这些函数是内建函数，经过了编译器的高度优化，运行速度十分快（有些甚至只需要一条指令）。

更多位数

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

题目推荐

Luogu P1225 黑白棋游戏

参考资料与注释

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

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

  2. 适用于 C++20 以前的标准。 ↩︎

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

  4. 一个数二进制表示从低往高的第一个 11 连同后面的零，如 (1010)2(1010)_2 的 lowbit 是 (0010)2(0010)_2，详见 树状数组。 ↩︎

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 32ms
  4. Powered by Hydro v4.19.1 Community