C++ 位运算

0. 概述

在现代计算机中，所有数据都以二进制形式存储，即 0 和 1 两种状态。计算机对二进制数据进行的运算（如加、减、乘、除）被称为位运算（Bitwise Operation），即对二进制数的每一位进行操作的运算。

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

运算	计算机符号	数学符号	语法	解释
按位与 ^[1]	`&`	$\&$ 、 $\mathrm{and}$	`x & y`	只有两个对应位都为 1 时，结果为 1
按位或 ^[2]	`\|`	$\|$ 、 $\mathrm{or}$	`x \| y`	只要两个对应位中有一个 1，结果为 1
按位异或	`^`	$⊕$ 、 $\mathrm{xor}$	`x ^ y`	只有两个对应位不同时，结果为 1（相同为 0）
按位取反	`~`	⛔	`~x`	0 变 1，1 变 0
左移	`<<`	⛔	`x << y`	`x` 的各二进位全部左移 `y` 位，高位丢弃，低位补 0
右移	`>>`	⛔	`x >> y`	`x` 各二进位全部右移 `y` 位，高位补 0 或符号位补齐

手动进行位运算

要手动执行任何二进制位运算，最简单的方法是将两个操作数排列如下：

1 2	0 1 0 1 OR (or whatever bitwise operation you are doing) 0 1 1 0

然后，将操作应用于每个比特列，并将结果写在下面：

0 1 1 1

1. 按位与、或、异或

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

Warning

注意和逻辑运算进行区分。位运算只关心二进制数，但逻辑运算考虑的是条件表达式的成立与否。

我们以一组例子来说明这三个运算：

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

Tip

异或运算的逆运算是它本身（即 “可逆运算”），也就是说连续两次异或同一个数，得到的结果不变，即 $a⊕b⊕b=a$

手动计算这三个运算时的方法

当进行按位或运算时，如果某一列中的任何位为 1，则该列的结果为 1。

当进行按位与运算时，如果一列中的所有位都是 1，则该列的结果为 1。

当进行按位异或运算时，如果某一列中有奇数个 1 位，则该列的结果为 1。

Tip

在计算机中，负数按补码 ^[3] 形式参与运算。

2. 按位取反

取反是对一个数 num 进行的位运算，即单目运算。它的作用是把 num 的二进制补码中的 0 和 1 全部取反，0 变为 1，1 变为 0。有符号整数的符号位在 ~ 运算中同样会取反。

示例（有符号整数）：

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

3. 左移和右移

什么？！运算符 >> 和 << 不是用于输入和输出的吗？

C++ 重载了这两个运算符作为流输入输出运算符，因为今天的程序通常不大量使用位左移和右移运算符来移位。查看操作对象的类型发现，>> 和 << 可以执行不同的行为。例如，如果左操作数是整型，那么 << 就知道执行位左移行为。如果左操作数是像 std::cout 这样的输出流对象，那么它就知道应该执行输出操作。

num << i 表示将 num 的二进制表示向左移动 i 位所得的值。高位丢弃，低位补 0。

num >> i 表示将 num 的二进制表示向右移动 i 位所得的值。高位补 0 或符号位补齐。

例如：

11=(00001011)_2 \\11<<3=(01011000)_2=88 \\11>>2=(00000010)_2=2

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

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

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

Example

这里我写了一个示例 C++ 程序：

#include <iostream>

int main(void)
{
    int test = 11; // (00001011)_2
    std::cout << (test << -1) << '\n' << (test << 32) << '\n';
    return 0;
}

Clang 对两个位运算均有 Warning 提示：Shift count is negative 和 Shift count >= width of type。

运行结果如下：

1 2	-2147483648 11

test << -1 整数溢出到极小负数；test << 32 疑似又移回来了。

接下来试试这个：

#include <iostream>

int main(void)
{
    int test = 11; // (00001011)_2
    std::cout << (test << 34) << '\n' << (test << 40) << '\n';
    return 0;
}

得到：

1
2

44
2816

越来越奇怪了……

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

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

4. 复合赋值位运算符

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

5. 优先级

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

6. 隐式类型转换问题

如果位运算符的操作数是小于 int 的整型类型，则这些操作数将被转换为 int 或 unsigned int ，返回的结果也将是 int 或 unsigned int 。例如，如果我们的操作数是 unsigned short ，则它们将被转换为 unsigned int ，操作的结果将以 unsigned int 返回。

当在比 int 或 unsigned int 更窄的整型类型上使用位运算符时，有两个情况需要注意：

~ 和 << 对操作数的宽度敏感，可能因操作数的宽度不同而产生不同的结果。
初始化或将结果分配给较小的整数类型变量是缩窄转换（因为将 int 或 unsigned int 转换为较小的整数类型可能会导致数据丢失）。这在列表初始化中是不允许的，并且编译器可能会或可能不会对缩窄赋值发出警告。

以下程序展示了这些问题（假设为 32 位整型）：

#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t c { 0b00001111 };

    std::cout << std::bitset<32>(~c) << '\n';     // incorrect: prints 11111111111111111111111111110000
    std::cout << std::bitset<32>(c << 6) << '\n'; // incorrect: prints 0000000000000000001111000000
    std::uint8_t cneg { ~c };                     // error: narrowing conversion from unsigned int to std::uint8_t
    c = ~c;                                       // possible warning: narrowing conversion from unsigned int to std::uint8_t

    return 0;
}

这些问题可以通过使用 static_cast 将位运算结果转换回更窄的整型来解决：

#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t c { 0b00001111 };

    std::cout << std::bitset<32>(static_cast<std::uint8_t>(~c)) << '\n';     // correct: prints 00000000000000000000000011110000
    std::cout << std::bitset<32>(static_cast<std::uint8_t>(c << 6)) << '\n'; // correct: prints 0000000000000000000011000000
    std::uint8_t cneg { static_cast<std::uint8_t>(~c) };                     // compiles
    c = static_cast<std::uint8_t>(~c);                                       // no warning

    return 0;
}

（来源：O.2 — Bitwise operators - LearnC++）

Warning

尽量避免在小于 int 的整型类型上使用位移动操作。

7. 应用

位运算一般有三种作用：

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

需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。

7.1 有关 2 的 n 次幂的问题

由于位运算针对的是变量的二进制位，因此可以推广出许多与 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。

7.2 使用位运算符和位掩码操作特定位

为了操作单个位，我们需要一种方法来识别我们想要操作的特定位。不幸的是，位运算会对数据的所有位生效，所以我们使用位掩码 (Bit masks)，让位运算只对目标位生效。

Note

类比于房间装修，当我们给墙面刷漆时，我们当然不想让窗户也沾上漆体。这时可以给窗户铺上一层塑料薄膜，避免漆体进入。这层塑料薄膜就是位掩码。

7.2.1 定义位掩码

最简单的位掩码集合是为每个位位置定义一个位掩码。我们使用 0 来屏蔽我们不关心的位，使用 1 来表示我们想要修改的位。

对于 C++14 及后续标准

因为 C++14 支持二进制字面量，定义这些位掩码很容易：

#include <cstdint>

constexpr std::uint8_t mask0{ 0b0000'0001 }; // represents bit 0
constexpr std::uint8_t mask1{ 0b0000'0010 }; // represents bit 1
constexpr std::uint8_t mask2{ 0b0000'0100 }; // represents bit 2
constexpr std::uint8_t mask3{ 0b0000'1000 }; // represents bit 3
constexpr std::uint8_t mask4{ 0b0001'0000 }; // represents bit 4
constexpr std::uint8_t mask5{ 0b0010'0000 }; // represents bit 5
constexpr std::uint8_t mask6{ 0b0100'0000 }; // represents bit 6
constexpr std::uint8_t mask7{ 0b1000'0000 }; // represents bit 7

现在我们有一组符号常量，代表每个比特位置。我们可以使用这些常量来操作比特。

对于 C++11 及之前标准

因为 C++11 不支持二进制字面量，我们必须使用其他方法来设置符号常量。这里有两种好的方法：

使用十六进制字面量

constexpr std::uint8_t mask0{ 0x01 }; // hex for 0000 0001
constexpr std::uint8_t mask1{ 0x02 }; // hex for 0000 0010
constexpr std::uint8_t mask2{ 0x04 }; // hex for 0000 0100
constexpr std::uint8_t mask3{ 0x08 }; // hex for 0000 1000
constexpr std::uint8_t mask4{ 0x10 }; // hex for 0001 0000
constexpr std::uint8_t mask5{ 0x20 }; // hex for 0010 0000
constexpr std::uint8_t mask6{ 0x40 }; // hex for 0100 0000
constexpr std::uint8_t mask7{ 0x80 }; // hex for 1000 0000

使用左移运算符

constexpr std::uint8_t mask0{ 1 << 0 }; // 0000 0001
constexpr std::uint8_t mask1{ 1 << 1 }; // 0000 0010
constexpr std::uint8_t mask2{ 1 << 2 }; // 0000 0100
constexpr std::uint8_t mask3{ 1 << 3 }; // 0000 1000
constexpr std::uint8_t mask4{ 1 << 4 }; // 0001 0000
constexpr std::uint8_t mask5{ 1 << 5 }; // 0010 0000
constexpr std::uint8_t mask6{ 1 << 6 }; // 0100 0000
constexpr std::uint8_t mask7{ 1 << 7 }; // 1000 0000

7.2.2 使用位掩码

查看位状态

使用 & 运算符。

#include <cstdint>
#include <iostream>

int main()
{
	[[maybe_unused]] constexpr std::uint8_t mask0{ 0b0000'0001 }; // represents bit 0
	[[maybe_unused]] constexpr std::uint8_t mask1{ 0b0000'0010 }; // represents bit 1
	[[maybe_unused]] constexpr std::uint8_t mask2{ 0b0000'0100 }; // represents bit 2
	[[maybe_unused]] constexpr std::uint8_t mask3{ 0b0000'1000 }; // represents bit 3
	[[maybe_unused]] constexpr std::uint8_t mask4{ 0b0001'0000 }; // represents bit 4
	[[maybe_unused]] constexpr std::uint8_t mask5{ 0b0010'0000 }; // represents bit 5
	[[maybe_unused]] constexpr std::uint8_t mask6{ 0b0100'0000 }; // represents bit 6
	[[maybe_unused]] constexpr std::uint8_t mask7{ 0b1000'0000 }; // represents bit 7

	std::uint8_t flags{ 0b0000'0101 }; // 8 bits in size means room for 8 flags

	std::cout << "bit 0 is " << (static_cast<bool>(flags & mask0) ? "on\n" : "off\n");
	std::cout << "bit 1 is " << (static_cast<bool>(flags & mask1) ? "on\n" : "off\n");

	return 0;
}

设置位（将位设置为 1）

使用 |= 运算符

#include <cstdint>
#include <iostream>

int main()
{
    [[maybe_unused]] constexpr std::uint8_t mask0{ 0b0000'0001 }; // represents bit 0
    [[maybe_unused]] constexpr std::uint8_t mask1{ 0b0000'0010 }; // represents bit 1
    [[maybe_unused]] constexpr std::uint8_t mask2{ 0b0000'0100 }; // represents bit 2
    [[maybe_unused]] constexpr std::uint8_t mask3{ 0b0000'1000 }; // represents bit 3
    [[maybe_unused]] constexpr std::uint8_t mask4{ 0b0001'0000 }; // represents bit 4
    [[maybe_unused]] constexpr std::uint8_t mask5{ 0b0010'0000 }; // represents bit 5
    [[maybe_unused]] constexpr std::uint8_t mask6{ 0b0100'0000 }; // represents bit 6
    [[maybe_unused]] constexpr std::uint8_t mask7{ 0b1000'0000 }; // represents bit 7

    std::uint8_t flags{ 0b0000'0101 }; // 8 bits in size means room for 8 flags

    std::cout << "bit 1 is " << (static_cast<bool>(flags & mask1) ? "on\n" : "off\n");

    flags |= mask1; // turn on bit 1

    std::cout << "bit 1 is " << (static_cast<bool>(flags & mask1) ? "on\n" : "off\n");

    flags |= (mask4 | mask5); // turn bits 4 and 5 on at the same time

    return 0;
}

清除位（将位设置为 0）

同时使用 &= 和 ~ 运算

#include <cstdint>
#include <iostream>

int main()
{
    [[maybe_unused]] constexpr std::uint8_t mask0{ 0b0000'0001 }; // represents bit 0
    [[maybe_unused]] constexpr std::uint8_t mask1{ 0b0000'0010 }; // represents bit 1
    [[maybe_unused]] constexpr std::uint8_t mask2{ 0b0000'0100 }; // represents bit 2
    [[maybe_unused]] constexpr std::uint8_t mask3{ 0b0000'1000 }; // represents bit 3
    [[maybe_unused]] constexpr std::uint8_t mask4{ 0b0001'0000 }; // represents bit 4
    [[maybe_unused]] constexpr std::uint8_t mask5{ 0b0010'0000 }; // represents bit 5
    [[maybe_unused]] constexpr std::uint8_t mask6{ 0b0100'0000 }; // represents bit 6
    [[maybe_unused]] constexpr std::uint8_t mask7{ 0b1000'0000 }; // represents bit 7

    std::uint8_t flags{ 0b0000'0101 }; // 8 bits in size means room for 8 flags

    std::cout << "bit 2 is " << (static_cast<bool>(flags & mask2) ? "on\n" : "off\n");

    flags &= ~mask2; // turn off bit 2

    std::cout << "bit 2 is " << (static_cast<bool>(flags & mask2) ? "on\n" : "off\n");

    flags &= ~(mask4 | mask5); // turn bits 4 and 5 off at the same time

    return 0;
}

翻转位

要翻转位状态（从 0 到 1 或从 1 到 0），我们使用 ^= 运算：

#include <cstdint>
#include <iostream>

int main()
{
    [[maybe_unused]] constexpr std::uint8_t mask0{ 0b0000'0001 }; // represents bit 0
    [[maybe_unused]] constexpr std::uint8_t mask1{ 0b0000'0010 }; // represents bit 1
    [[maybe_unused]] constexpr std::uint8_t mask2{ 0b0000'0100 }; // represents bit 2
    [[maybe_unused]] constexpr std::uint8_t mask3{ 0b0000'1000 }; // represents bit 3
    [[maybe_unused]] constexpr std::uint8_t mask4{ 0b0001'0000 }; // represents bit 4
    [[maybe_unused]] constexpr std::uint8_t mask5{ 0b0010'0000 }; // represents bit 5
    [[maybe_unused]] constexpr std::uint8_t mask6{ 0b0100'0000 }; // represents bit 6
    [[maybe_unused]] constexpr std::uint8_t mask7{ 0b1000'0000 }; // represents bit 7

    std::uint8_t flags{ 0b0000'0101 }; // 8 bits in size means room for 8 flags

    std::cout << "bit 2 is " << (static_cast<bool>(flags & mask2) ? "on\n" : "off\n");
    flags ^= mask2; // flip bit 2
    std::cout << "bit 2 is " << (static_cast<bool>(flags & mask2) ? "on\n" : "off\n");
    flags ^= mask2; // flip bit 2
    std::cout << "bit 2 is " << (static_cast<bool>(flags & mask2) ? "on\n" : "off\n");

    return 0;
}