说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C4-Binary/bitwise.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
4.6. Bitwise Operators
除了前面介绍的标准算术运算之外,CPU 还支持一些在二进制之外很少见的运算。这些位运算符(bitwise operator)直接把逻辑门的行为应用到位序列上,因此可以直接、高效地用硬件实现。程序员通常用加法和减法来处理变量的数值含义,而位运算符则通常用来修改变量中的特定位。例如,程序可能把变量中的某个位编码为表示真/假的含义,位运算让程序可以操作变量中的单个位,从而修改那个特定的位。
In addition to the standard arithmetic operations described earlier, CPUs also support operations that are uncommon outside of binary. These bitwise operators directly apply the behavior of logic gates to bit sequences, making them straightforward to implement efficiently in hardware. Unlike addition and subtraction, which programmers typically use to manipulate a variable’s numerical interpretation, programmers commonly use bitwise operators to modify specific bits in a variable. For example, a program might encode a certain bit position in a variable to hold a true/false meaning, and bitwise operations allow the program to manipulate the variable’s individual bits to change that specific bit.
4.6.1. 按位与
4.6.1. Bitwise AND
按位与运算符(&)对两个输入位序列求值。对于输入的每一位,如果两个输入在该位置上都是 1,就在输出的对应位置输出 1,否则在该位输出 0。表 1 给出了两个值 A 和 B 按位与的真值表。
The bitwise AND operator (
&) evaluates two input bit sequences. For each digit of the inputs, it outputs a 1 in the corresponding position of the output if both inputs are 1 in that position. Otherwise, it outputs a 0 for the digit. Table 1 shows the truth table for the bitwise AND of two values, A and B.
表 1. 两个值按位与的结果(A AND B)
Table 1. The Results of Bitwise ANDing Two Values (A AND B)
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
例如,要对 0b011010 和 0b110110 按位与,先把两个序列对齐。逐位纵向检查,如果两位都是 1,就把该列的结果设为 1,否则设为 0:
For example, to bitwise AND 0b011010 with 0b110110, start by lining up the two sequences. Checking vertically through each digit, set the result of the column to 1 if both digits are 1. Otherwise, set the result of the column to 0:
1 | 011010 |
要在 C 中进行按位与,就把 C 的按位与运算符(&)放在两个操作数变量之间。下面用 C 实现同一个例子:
To perform a bitwise AND in C, place C’s bitwise AND operator (
&) between two operand variables. Here’s the same example again, performed in C:
1 | int x = 26; |
原书警示 · 位运算与逻辑真值运算(Bitwise Operations versus Logical Truth Operations)
小心不要把位运算符和逻辑真值运算符混为一谈。尽管它们的名字相似(AND、OR、NOT 等),两者并不相同:
位运算符独立地考虑输入的每一位,产生的输出位序列取决于输入中具体哪些位被置为 1。
逻辑运算符只考虑操作数的真值解释。对 C 来说,值为零就是假,其他所有值都被视为真。逻辑运算符常用于对条件求值(例如
if语句)。
注意,C 常常用相似(但略有不同)的运算符来区分这两者。例如,用单个 & 和 | 分别表示按位与和按位或,而逻辑与和逻辑或对应的是两个字符的 && 和 ||。最后,按位取反用 ~,而逻辑非用 ! 表示。
Be careful not to conflate bitwise operators with logical truth operators. Despite having similar names (AND, OR, NOT, etc.), the two are not the same:
Bitwise operators consider each bit of their inputs independently and produce an output bit sequence as a function of the specific input bits that are set.
Logical operators consider only the truth interpretation of their operands. To C, a value of zero is false, whereas all other values are considered true. Logical operators are often used when evaluating conditionals (e.g.,
ifstatements).Note that C often uses similar (but slightly different) operators to distinguish between the two. For example, you can indicate bitwise AND and bitwise OR using a single
&and|, respectively. Logical AND and logical OR correspond to a double&&and||. Finally, bitwise NOT uses~, whereas logical NOT is expressed by!.
4.6.2. 按位或
4.6.2. Bitwise OR
按位或运算符(|)的行为与按位与运算符类似,只是只要两个输入在对应位置上任一个或都是 1,它就在该位输出 1,否则输出 0。表 2 给出了两个值 A 和 B 按位或的真值表。
The bitwise OR operator (
|) behaves like the bitwise AND operator except that it outputs a 1 for a digit if either or both of the inputs is 1 in the corresponding position. Otherwise, it outputs a 0 for the digit. Table 2 shows the truth table for the bitwise OR of two values, A and B.
表 2. 两个值按位或的结果(A OR B)
Table 2. The Results of Bitwise ORing Two Values (A OR B)
| A | B | A | B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
例如,要对 0b011010 和 0b110110 按位或,先把两个序列对齐。逐位纵向检查,如果任一位是 1,就把该列的结果设为 1:
For example, to bitwise OR 0b011010 with 0b110110, start by lining up the two sequences. Checking vertically through each digit, set the result of the column to 1 if either digit is 1:
1 | 011010 |
要在 C 中进行按位或,就把 C 的按位或运算符(|)放在两个操作数之间。下面用 C 实现同一个例子:
To perform a bitwise OR in C, place C’s bitwise OR operator (
|) between two operands. Here’s the same example again, performed in C:
1 | int x = 26; |
4.6.3. 按位异或(XOR)
4.6.3. Bitwise XOR (Exclusive OR)
按位异或运算符(^)的行为与按位或运算符类似,只是只有当两个输入在对应位置上恰好有一个(而不是两个都)为 1 时,它才在该位输出 1,否则输出 0。表 3 给出了两个值 A 和 B 按位异或的真值表。
The bitwise XOR operator (
^) behaves like the bitwise OR operator except that it outputs a 1 for a digit only if exactly one (but not both) of the inputs is 1 in the corresponding position. Otherwise, it outputs a 0 for the digit. Table 3 shows the truth table for the bitwise XOR of two values, A and B.
表 3. 两个值按位异或的结果(A XOR B)
Table 3. The Results of Bitwise XORing Two Values (A XOR B)
| A | B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
例如,要对 0b011010 和 0b110110 按位异或,先把两个序列对齐。逐位纵向检查,如果只有一位是 1,就把该列的结果设为 1:
For example, to bitwise XOR 0b011010 with 0b110110, start by lining up the two sequences. Checking vertically through each digit, set the result of the column to 1 if only one digit is 1:
译注
下面代码注释中的「Digits 2, 3, and 6」应为「2、3 和 5」:结果 101100 中为 1 的是第 5、3、2 位(从右往左、从 0 开始数),六位数里并没有第 6 位。
1 | 011010 |
要在 C 中进行按位异或,就把 C 的按位异或运算符(^)放在两个操作数之间。下面用 C 实现同一个例子:
To perform a bitwise XOR in C, place C’s bitwise XOR operator (
^) between two operands. Here’s the same example again, performed in C:
1 | int x = 26; |
4.6.4. 按位取反
4.6.4. Bitwise NOT
按位取反运算符(~)只作用于一个操作数。对于序列中的每一位,它只是把这一位翻转,0 变成 1,1 变成 0。表 4 给出了按位取反运算符的真值表。
The bitwise NOT operator (
~) operates on just one operand. For each bit in the sequence, it simply flips the bit such that a zero becomes a one or vice versa. Table 4 shows the truth table for the bitwise NOT operator.
表 4. 对一个值(A)按位取反的结果
Table 4. The Results of Bitwise NOTing a Value (A)
| A | ~ A |
|---|---|
| 0 | 1 |
| 1 | 0 |
例如,要对 0b011010 按位取反,就把每一位的值取反:
For example, to bitwise NOT 0b011010, invert the value of each bit:
1 | NOT 011010 |
要在 C 中进行按位取反,就在操作数前面加上波浪号(~)。下面用 C 实现同一个例子:
To perform a bitwise NOT in C, place a tilde character (
~) in front of an operand. Here’s the same example again, performed in C:
1 | int x = 26; |
原书警示 · 按位取反与取负(Bitwise NOT vs. Negation)
注意,所有现代系统都用补码表示整数,所以按位取反与取负并不完全一样。按位取反只翻转各位,不加一。
Note that all modern systems represent integers using two’s complement, so bitwise NOT isn’t quite the same as negation. Bitwise NOT only flips the bits and doesn’t add one.
4.6.5. 移位
4.6.5. Bit Shifting
另一种重要的位运算是把操作数的各位向左(<<)或向右(>>)移动。左移和右移运算符都接收两个操作数:要移位的位序列,以及要移动的位数。
Another important bitwise operation involves shifting the position of an operand’s bits either to the left (
<<) or to the right (>>). Both the left and right shifting operators take two operands: the bit sequence to shift and the number of places it should be shifted.
左移
Shifting Left
把一个序列左移 N 位,会把它的每一位都向左移动 N 次,并在序列的右端补上新的零。例如,把八位序列 0b00101101 左移两位得到 0b10110100。右边的两个零被补在序列的末尾,因为结果仍然需要是一个八位序列。
Shifting a sequence to the left by N places moves each of its bits to the left N times, appending new zeros to the right side of the sequence. For example, shifting the eight-bit sequence 0b00101101 to the left by two produces 0b10110100. The two zeros at the right are appended to end of the sequence, since the result still needs to be an eight-bit sequence.
在没有溢出的情况下,左移会使结果的值增大,因为各位都移向了对数值贡献更大的 2 的幂的数位。但是,在位数固定的情况下,任何移到数的最大容量之外的位都会被截断。例如,把八位序列 0b11110101(无符号解释为 245)左移一位,得到 0b11101010(无符号解释为 234)。在这里,被移出去的高位被截断,使结果变小了。
In the absence of overflow, shifting to the left increases the value of the result because bits move toward digits that contribute larger powers of two to the value of the number. However, with a fixed number of bits, any bits that shift into positions beyond the maximum capacity of the number get truncated. For example, shifting the eight-bit sequence 0b11110101 (unsigned interpretation 245) to the left by one produces 0b11101010 (unsigned interpretation 234). Here, the truncation of the high-order bit that shifted out makes the result smaller.
要在 C 中进行左移,就在一个值和要移动的位数之间放上两个小于号(<<):
To perform a left bit shift in C, place two less-than characters (
<<) between a value and the number of places to shift that value:
1 | int x = 13; // 13 is 0b00001101 |
右移
Shifting Right
右移与左移类似——任何移出变量容量之外的位(例如从右端移出去的位)都会因截断而消失。不过,右移还要额外考虑一点:在结果左侧补上的新位,可能需要全是零,也可能需要全是一,这取决于被移位变量的类型及其高位的值。从概念上讲,选择补零还是补一,与符号扩展类似。因此,右移有两种不同的变体:
Shifting to the right is similar to left shifting — any bits that are shifted out of a variable’s capacity (e.g., off the end to the right) disappear due to truncation. However, right shifting introduces an additional consideration: the new bits prepended to the left side of the result may need to be either all zeros or all ones depending on the type of the variable being shifted and its high-order bit value. Conceptually, the choice to prepend zeros or ones resembles that of sign extension. Thus, there exist two distinct variants of right shifting:
- 逻辑右移(logical right shift)总是在结果的高位补零。逻辑移位用于移动无符号变量,因为无符号值最高有效位上的 1 并不表示这个值是负数。例如,用逻辑移位把 0b10110011 右移两位,得到 0b00101100。
- A logical right shift always prepends zeros to the high-order bits of the result. Logical shifting is used to shift unsigned variables, since a leading 1 in the most significant bit of an unsigned value isn’t intended to mean that the value is negative. For example, shifting 0b10110011 to the right by two using a logical shift yields 0b00101100.
- 算术右移(arithmetic right shift)在每个新的位位置上都补上被移位值最高有效位的副本。算术移位适用于有符号变量,对它们来说,保持高位的符号很重要。例如,用算术移位把 0b10110011 右移两位,得到 0b11101100。
- An arithmetic right shift prepends a copy of the shifted value’s most significant bit into each of the new bit positions. Arithmetic shifting applies to signed variables, for which it’s important to preserve the signedness of the high-order bits. For example, shifting 0b10110011 to the right by two using an arithmetic shift yields 0b11101100.
幸运的是,在用 C 编程时,只要正确地声明了变量,通常就不必操心这一区别。如果你的程序中有右移运算符(>>),几乎所有 C 编译器都会根据被移位变量的类型自动执行相应类型的移位。也就是说,如果被移位的变量是用 unsigned 限定符声明的,编译器就执行逻辑移位,否则执行算术移位。
Fortunately, when programming in C, you don’t typically need to worry about the distinction if you’ve declared your variables properly. If your program includes a right shift operator (
>>), virtually every C compiler will automatically perform the appropriate type of shifting according to the type of the shifting variable. That is, if the shifting variable was declared with the unsigned qualifier, the compiler will perform a logical shift. Otherwise, it will perform an arithmetic shift.
译注
严格地说,C 标准规定:对负的有符号数右移,结果由实现定义(implementation-defined);GCC 和 Clang 都实现为算术右移,所以原书说的「几乎所有编译器」是准确的。另外,对负数左移、或移位位数大于等于类型宽度,在 C 中是未定义行为,写代码时要避免。
原书注 · C 右移示例程序(C Right Shift Example Program)
你可以用下面这样的一个小示例程序来测试右移的行为:
1 | #include <stdio.h> |
这个程序声明了两个 32 位整数:一个是无符号整数(u_val),另一个是有符号整数(s_val)。它把两个整数都初始化为同一个初始值:八个一后面跟着 24 个零(0b1111111100000000000000000000000000),然后把两个值都右移 12 位。执行时它会打印:
1 | $ ./a.out |
由于对无符号的 u_val 来说,开头的 1 并不表示「负数」,编译器使用的指令只在前面补零。移位结果包含 12 个零、八个一,再跟 12 个零(0b00000000000011111111000000000000)。另一方面,对 s_val 来说,开头的 1 确实表示「负数」,所以编译器在移位后的值前面补 1,得到 20 个一后面跟着 12 个零(0b11111111111111111111000000000000)。
You can test the behavior of right shifting with a small example program like this one:
1
2
3
4
5
6
7
8
9
10
11
12
13
14 #include <stdio.h>
int main(int argc, char **argv) {
/* Unsigned integer value: u_val. */
unsigned int u_val = 0xFF000000;
/* Signed integer value: s_val. */
int s_val = 0xFF000000;
printf("%08X\n", u_val >> 12); // logical right shift
printf("%08X\n", s_val >> 12); // arithmetic right shift
return 0;
}This program declares two 32-bit integers: one as an unsigned integer (
u_val), and another as a signed integer (s_val). It initializes both integers to the same starting value: a sequence of eight ones followed by 24 zeros (0b1111111100000000000000000000000000), and then it shifts both values 12 positions to the right. When executed, it prints:
1
2
3 $ ./a.out
000FF000
FFFFF000Because a leading 1 doesn’t indicate “negative” for the unsigned
u_val, the compiler uses instructions to prepend it with only zeros. The shifted result contains 12 zeros, eight ones, and 12 more zeros (0b00000000000011111111000000000000). On the other hand, the leading 1 does indicate “negative” fors_val, so the compiler prepends 1’s to the front of the shifted value, yielding 20 ones followed by 12 zeros (0b11111111111111111111000000000000).
译注
文中 0b1111111100000000000000000000000000 实际写了 8 个一和 26 个零(共 34 位),正确的 32 位值应是 8 个一加 24 个零:0b11111111000000000000000000000000。程序本身没有问题,译者在 macOS 上运行,输出同样是 000FF000 和 FFFFF000。