简介
位操作
整数的每一位都可以用来存储一个二进制值。
由于很多情况都涉及二进制信息，比如 true 或 false、包含或排除、开或关，因此 N 位整数的二进制表示提供了一种紧凑的方式，用来编码 N 个条目的二进制状态。
这使得在汇编中操作位和字节的能力必不可少。
x86-64 指令集提供了种类丰富的位操作指令。
单个位的操作
这些指令作用于操作数中的单个位。
它们都接受两个操作数，第二个操作数指明在第一个操作数中要操作的位的下标。
它们都会把选中的位复制到**进位标志（CF）**中。
| 名称 |
说明 |
bt |
把该位复制到CF，不修改任何操作数 |
bts |
把该位复制到CF，并在目标操作数中把它置位 |
btr |
把该位复制到CF，并在目标操作数中把它清零 |
btc |
把该位复制到CF，并在目标操作数中把它取反（翻转） |
按位运算
按位运算作用于操作数的所有位。
它们各自都有一条指令，名称与所执行的按位运算相同：
| 名称 |
说明 |
and |
两个位都为 1 时结果为 1 |
or |
至少有一个位为 1 时结果为 1 |
xor |
两个位不同时结果为 1 |
not |
位为 0 时结果为 1；位为 1 时结果为 0 |
它们中大多数接受两个操作数，对两者执行按位运算，并把结果存入目标操作数。
例外的是not，它只接受一个目标操作数。
掩码
当我们把 1 和 0 分别解释为包含和排除时，这样的整数就称为_位掩码_（或简称为_掩码_）。
位掩码会“屏蔽掉”条目：第i位为 0 表示排除第i个条目，为 1 则表示包含。
我们也常用位掩码来包含整数的某些位，同时排除其他位。
例如，设A是一个整数，其二进制表示为：
| 下标 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| 位 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
再设M是一个整数，其二进制表示为：
| 下标 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
| 位 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
两者都是8位整数。
在这种情况下，我们可以说M选中了A的0、2和3位，排除了其余的位。
前面讨论的按位指令在配合掩码操作整数时很有用。
例如：
- 要清除
A中未被M选中的位，执行按位 AND：A AND M。
- 要置位
A中被M选中的位，执行按位 OR：A OR M。
test 指令
test指令对两个操作数执行按位 AND，并根据结果设置标志位。
如果 A 是第一个操作数，B 是第二个操作数：
| 标志 |
置位条件 |
CF |
始终清零 |
ZF |
A AND B == 0 |
SF |
A AND B 的符号位被置位 |
OF |
始终清零 |
这条指令接受两个操作数并更新标志位，但不会修改它的操作数。
移位操作
这些指令按照第二个操作数指定的位数移动目标操作数中的位。
第二个操作数必须是一个常数（即immediate）或寄存器cl（rcx的最低8位）。
| 名称 |
说明 |
shl/sal
|
向左移位 |
shr/sar
|
向右移位 |
注意，第二个操作数中的移位次数会被掩码为5位，若目标操作数为64位则为6位。
超出这个范围的位都会被忽略。
这意味着最大移位量是31，若操作数为64位则为63。
Shl / Sal
shl和sal执行完全相同的操作，其中一个是另一个的别名。
每当执行左移时，序列末端处、数量等于移位长度的那些位会先被移入CF，然后被丢弃。
与此同时，序列开头会补上数量等于移位长度的、已清零的新位。
由于整数中的每一位都代表2的幂，向左移动 n 位相当于把该整数乘以2ⁿ。
Shr / Sar
有两条把位向右移动的指令：shr和sar。
每次使用这两条指令中的任何一条时，序列起始处、数量等于移位长度的那些位会先被移入CF，然后被丢弃。
与此同时，序列末端会补上数量等于移位长度的新位。
两者的区别在于，shr会在左端补0，而sar在最高位被置位时补1，否则补0。
这意味着sar在有符号整数移位时能保留符号。
由于整数中的每一位都代表2的幂，用shr向右移动 n 位相当于执行一次无符号除法，除以2ⁿ。
同样，用sar向右移动 n 位相当于执行一次有符号除法，除以2ⁿ。
循环移位操作
这些指令按照第二个操作数指定的位数移动目标操作数中的位。
第二个操作数必须是一个常数（即immediate）或寄存器cl（rcx的最低8位）。
循环移位与移位的区别在于，循环移位不会丢弃或新增任何位。
移位会丢弃的那些位会被移到另一端。
因此所有位都保留下来，只是都换了位置。
| 名称 |
说明 |
rol |
向左循环移位 |
ror |
向右循环移位 |
注意，第二个操作数中的移位次数会被掩码为5位，若目标操作数为64位则为6位。
超出这个范围的位都会被忽略。
这意味着最大循环移位量是31，若操作数为64位则为63。
其他位操作指令
还有其他有用的位操作指令：
| 名称 |
说明 |
popcnt |
统计被置位的位数 |
bsr |
获取最高置位位的下标。如果没有位被置位，结果是未定义的 |
bsf |
获取最低置位位的下标。如果没有位被置位，结果是未定义的 |
这些指令都处理两个16位、32位或64位操作数。
它们不能用于8位操作数。
说明
你的朋友刚刚给你发来一条带有重要秘密的消息。
为了让别人不那么容易读懂它，这条消息在加密时进行了一系列位运算操作。
你需要编写这些方法来帮助解密这条消息。
以下是本概念中提到的单比特指令：
| 名称 |
描述 |
| bt |
在不修改任何操作数的情况下，把该位复制到 CF
|
| bts |
把该位复制到 CF，并在目标操作数中将它置 1 |
| btr |
把该位复制到 CF，并在目标操作数中将它清 0 |
| btc |
把该位复制到 CF，并在目标操作数中将它取反（翻转） |
以下是本概念中提到的位运算指令：
| 名称 |
描述 |
| and |
两个位都为 1 时结果为 1 |
| or |
两个位中至少有一个为 1 时结果为 1 |
| xor |
两个位不同时结果为 1 |
| not |
位为 0 时结果为 1；位为 1 时结果为 0 |
以下是本概念中提到的移位指令：
| 名称 |
描述 |
| shl/sal |
把位向左移 |
| shr/sar |
把位向右移 |
以下是本概念中提到的旋转指令：
| 名称 |
描述 |
| rol |
把位向左旋转 |
| ror |
把位向右旋转 |
以下是本概念中提到的其他指令：
| 名称 |
描述 |
| popcnt |
统计被置 1 的位数 |
| bsr |
获取最高有效置 1 位的下标。如果没有位被置 1，结果为未定义 |
| bsf |
获取最低有效置 1 位的下标。如果没有位被置 1，结果为未定义 |
1. 提取掩码
这条消息被编码在一个 16 位整数中。
不过，其中最高的 8 位其实并不属于消息，而是一个需要在解密时用到的掩码。
实现 extract_higher_bits 函数，它接收一个 16 位整数，并返回其中最高的 8 位。
extract_higher_bits(0b1010010011000101)
// => 0b10100100
2. 提取消息
仅仅能够提取掩码还不够，你还应该把消息单独分离出来。
实现 extract_lower_bits 函数，它接收一个 16 位整数，并返回其中最低的 8 位。
extract_lower_bits(0b1010010011000101);
// => 0b11000101
3. 提取冗余位
消息和掩码中都有一些位被置 1。
这是一条非常重要的信息，后面会用到。
实现 extract_redundant_bits，它接收一个 16 位整数（同时编码了消息和一个掩码），并返回一个只把冗余位置 1 的 8 位整数。
在返回的数字中，如果某一位在消息和掩码中同样都是 1，那么该位应置为 1。
其他所有位都应_清 0_。
extract_redundant_bits(0b1010010011000101);
// => 0b10000100
4. 设置消息中的所有位
接下来，根据掩码，消息中有一些位需要置为 1。
实现 set_message_bits 函数，它接收一个 16 位整数（同时编码了消息和一个掩码），并返回把消息中的位置为 1 之后的结果。
当掩码中的某一位为 1 时，消息中对应的位应置为 1。
其他所有位应保持_不变_，也就是说，原本置 1 的仍然置 1，原本清 0 的仍然清 0。
set_message_bits(0b1010010011000101);
// => 0b11100101
5. 旋转私钥
还有一块拼图并没有明确出现在消息里：16 位数字 0b1011001100111100。
这个数字就是你共享的私钥，你应该用它来帮助解密消息。
为此，你首先需要把私钥的位向左旋转若干个位置。
旋转的位置数等于消息和掩码中同时置 1 的冗余位的数量。
实现 rotate_private_key 函数，它接收一个 16 位整数（同时编码了消息和一个掩码），并返回旋转私钥后的结果。
这个结果是一个 16 位整数。
rotate_private_key(0b1010010011000101);
// => 0b1100110011110010
NASM（The Netwide Assembler，本练习所用的汇编器）支持用 0b 前缀表示二进制格式的常量。
它还支持在常量中使用下划线（_）作为分隔符，以提高可读性：
PRIVATE_KEY equ 0b1011_0011_0011_1100
6. 格式化私钥
为了能在解密中使用，你的私钥必须经过格式化，以分离出相关的位。
要完整地格式化一个私钥，你必须：
- 旋转它。
- 分离出旋转后私钥中最低的 8 位，这就是基值。
- 分离出旋转后私钥中最高的 8 位，这是一个要作用于基值的掩码。
- 翻转基值中那些在掩码里同样被置 1 的位。
- 翻转结果中的所有位。
翻转后的位：如果原来是 0，则变成 1；如果原来是 1，则变成 0。
实现 format_private_key 函数，它接收一个 16 位整数（同时编码了消息和一个掩码），并返回一个完全格式化后的 8 位私钥。
format_private_key(0b1010010011000101);
// => 0b11000001
7. 完成解密
当你拿到置好所有相关位的消息和格式化后的私钥后，就可以把它们组合起来，得到最终的消息。
得到的消息是一个 16 位整数，其中：
- 最高的 8 位由格式化后的私钥填充。
- 最低的 8 位由设置好所有相关位之后的消息填充。
实现 decrypt_message 函数，它接收一个同时编码了消息和一个掩码的 16 位整数，并返回一个消息被完全解密后的 16 位整数。
这个函数应该用到你用 format_private_key 生成的格式化私钥，以及你用 set_message_bits 设置好所有相关位之后的消息。
decrypt_message(0b1010010011000101);
// => 0b1100000111100101
学习练习
