位与数学库 · Topos Uranos

摘要

对处理器来说，整数是一串位，而 C++ 提供了逐列作用于这串位的运算符：&、|、^ 和 ~，以及移位 << 和 >>。本课教你如何手工计算它们，如何用掩码技术把多个标志保存在一个整数中，以及如何识别标准没有定义的移位。接着解释为什么 2 ^ 3 等于 1 而不是 8，以及为什么位运算符需要括号。后半部分介绍数学库：<cmath> 的函数、<numbers> 的常量、<numeric> 中的最大公因数和最小公倍数，以及 <bit> 的位函数，并给出一条适用于任何语言的原则：库中已经提供的、正确且经过测试的东西不要重写。

学习目标

对较小的整数手工计算 &、|、^、~ 以及移位的结果。
区分有定义的移位（包括自 C++20 起对负数的移位）和属于未定义行为的移位，并预测前者的结果。
用掩码查询、置位、清零和翻转一个位。
解释为什么 2 ^ 3 等于 1 而不是 8，并根据情况在 std::pow 和移位之间作出选择。
在公式中使用 <cmath> 的函数（std::sqrt、std::pow、std::abs、std::hypot、三角函数）以及 <numbers> 的常量，如 std::numbers::pi。

位运算符

整数及其表示一课表明，int 是一串位，在本课程使用的系统中有 32 位，它的值是所有为 1 的位置的权之和。然而到目前为止，程序只把整数当作数来处理：对它做加法、乘法和除法。不过，同一串位还可以有另一种读法，即看作 32 个“是或否”的回答；针对这种读法，C++ 有四个逐位工作的运算符，各位置之间没有进位。

位从右边开始编号，从 0 起：位 $k$ 是权为 $2^k$ 的那一位。因此在 $12$ （二进制写作 1100）中，第 2 位和第 3 位为 1，第 0 位和第 1 位为 0。

运算符如下。按位与 a & b 在 a 和 b 都为 1 的每个位置上为 1。按位或 a | b 在两者中至少有一个为 1 的位置上为 1。按位异或 a ^ b 在两者中恰有一个为 1 的位置上为 1，也就是两位不同的地方。按位取反 ~a 只有一个操作数，它把每一位翻转。对一对位 $p$ 和 $q$ 而言，前三个运算符的表就是合取、析取和不可兼析取的真值表：

\begin{array}{cc|ccc} p & q & p \mathbin{\&} q & p \mid q & p \mathbin{\hat{}} q \\ \hline 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}

学过《数理逻辑 I》课程的人会在这里认出命题联结词，其中 1 表示真，0 表示假：位运算符不过是同时作用于所有列的联结词。由此得出手工计算的方法：把两个数写成二进制，上下对齐，右端对齐，然后在每一列上应用真值表，不必理会相邻的列。

例题十二和十，逐列计算

数 $12 =$ 1100 和 $10 =$ 1010 有这样的性质：它们的四列恰好遍历两个位的四种组合；所以用它们可以同时看到三张表。

证明

数据：1100 是 12，1010 是 10。各列从左到右依次是数对 $(1, 1)$ 、 $(1, 0)$ 、 $(0, 1)$ 和 $(0, 0)$ 。
12 & 10 的第一列：两位都是 1，与运算得 1。
第二列：1 和 0。只要有一个 0，与运算就得 0。
第三列：0 和 1；与运算又得 0。
第四列：0 和 0 得 0。结果这一行 1000 是 8：12 & 10 等于 8。
或运算把至少有一个 1 的每一列置为 1：1110，也就是说 12 | 10 等于 14。
异或只把两位不同的列置为 1：0110，12 ^ 10 等于 6。

下面的程序验证了这张图。格式字段 {:04b} 在讲整数的那一课中介绍过，它以二进制写出一个值，共四位数字，不足的用零补齐。

C++ 程序

#include <print>int main(){    const int a{0b1100};    const int b{0b1010};    std::println("a     = {:04b} = {}", a, a);    std::println("b     = {:04b} = {}", b, b);    std::println("a & b = {:04b} = {}", a & b, a & b);    std::println("a | b = {:04b} = {}", a | b, a | b);    std::println("a ^ b = {:04b} = {}", a ^ b, a ^ b);    std::println("~a    = {}", ~a);}

输出

a     = 1100 = 12b     = 1010 = 10a & b = 1000 = 8a | b = 1110 = 14a ^ b = 0110 = 6~a    = -13

最后一行需要解释。取反会翻转 a 的全部 32 位，而不只是写出来的四位：左边的 28 个零变成了一，而以 1 开头的 int 在二进制补码中是负数。而在二进制补码中，一个数的相反数是把它的各位取反再加 1 得到的，即 $-x = {\sim}x + 1$ ；因此 ${\sim}x = -x - 1$ ，~12 等于 $-13$ 。所以，对有符号整数按位取反得到的数，作为数很少有用：它作为位模式才有用，因此位操作最好在无符号类型中进行，在讲掩码的那一节会看到这一点。

关于小类型的一个提醒。运算之前，C++ 会把较窄整数类型（如 std::uint8_t）的每个操作数转换为 int；这就是算术运算一课为算术运算描述的提升，在这里同样适用。由此可知，当 flags 的类型为 std::uint8_t、值为 5 时，~flags 不是字节 11111010，而是 int 值 $-6$ ，它的 32 位中包括左边添上的 24 个一；只有把它重新存入 std::uint8_t 时，才会截成八位，得到预期的字节 250。

不要把位运算符与关系与逻辑一课的逻辑运算符混淆。6 && 3 是 true：两个操作数都不为零，结果是 bool。而 6 & 3 是一个整数，由两者都为 1 的那些列构成。此外，&& 按短路求值，而 & 总是对两个操作数都求值。