如果只需要结果的低位部分，可以使用哪个 2 的补码整数运算而无需将输入中的高位归零？
Which 2's complement integer operations can be used without zeroing high bits in the inputs, if only the low part of the result is wanted?
在汇编编程中，想要从寄存器的低位计算一些东西是很常见的，但不能保证其他位都为零。在像 C 这样的高级语言中，您只需将输入转换为小尺寸，让编译器决定是否需要分别将每个输入的高位置零，或者是否可以在事实上。
由于各种原因1，这对于 x86-64（又名 AMD64）尤其常见，其中一些存在于其他 ISA 中。
我将使用 64 位 x86 作为示例，但目的是询问 about/discuss 2's complement and unsigned binary arithmetic in general, since all modern CPUs use it。 （请注意，C 和 C++ 不保证补码 4，并且有符号溢出是未定义的行为。）
例如，考虑一个可以编译为 LEA 指令2 的简单函数。 （在 x86-64 SysV(Linux) ABI3 中，前两个函数参数在 rdi 和 rsi 中， rax 中的 return。int 是 32 位类型。）
; int intfunc(int a, int b) { return a + b*4 + 3; }
intfunc:
lea eax, [edi + esi*4 + 3] ; the obvious choice, but gcc can do better
ret
gcc 知道加法，即使是负符号整数，也只是从右到左进位，所以输入的高位不会影响进入 eax 的内容。因此，it saves an instruction byte and useslea eax, [rdi + rsi*4 + 3]
还有哪些运算的结果低位 属性 不依赖于输入的高位？
为什么它有效？
脚注
1 为什么 x86-64 经常出现这个问题：
x86-64 具有可变长度指令，其中额外的前缀字节会改变操作数的大小（从 32 到 64 或 16），因此在以相同速度执行的指令中通常可以节省一个字节。在写入寄存器的低位 8b 或 16b 时（或稍后读取完整寄存器（Intel pre-IvB）时停顿），它也具有错误依赖性（AMD/P4/Silvermont）：出于历史原因，only writes to 32b sub-registers zero the rest of the 64b register .几乎所有算术和逻辑都可以用在通用寄存器的低 8、16 或 32 位以及完整的 64 位上。整数向量指令也相当非正交，某些操作不适用于某些元素大小。
此外，与 x86-32 不同，ABI 在寄存器中传递函数参数，对于窄类型，高位不需要为零。
2 LEA:和其他指令一样，LEA的默认操作数大小是32bit，但是默认地址大小是64位。操作数大小前缀字节（0x66 或 REX.W）可以使输出操作数大小为 16 位或 64 位。地址大小前缀字节 (0x67) 可以将地址大小减少到 32 位（在 64 位模式下）或 16 位（在 32 位模式下）。所以在 64 位模式下，lea eax, [edx+esi] 比 lea eax, [rdx+rsi].
多占用一个字节
可以做到lea rax, [edx+esi]，但地址仍然只用 32 位计算（进位不会设置 rax 的第 32 位）。使用 lea eax, [rdx+rsi] 可以得到相同的结果，后者少了两个字节。因此，地址大小前缀对 LEA 永远没有用，正如 Agner Fog 出色的 objconv 反汇编程序的反汇编输出中的注释警告的那样。
3 x86 ABI：
调用者 不必 将用于按值传递或 return 较小类型的 64 位寄存器的上半部分归零（或符号扩展）。想要使用 return 值作为数组索引的调用者必须对其进行符号扩展（使用 movzx rax, eax 或 extra-case-for-eax 指令 cdqe。（不是与 cdq 混淆，后者将 eax 符号扩展为 edx:eax，例如设置 idiv。))
这意味着 returning unsigned int 函数可以在 rax 中的 64 位临时值中计算其 return 值，而不需要 mov eax, eax to zero the upper bits 共 rax。这种设计决策在大多数情况下都适用：调用者通常不需要任何额外的指令来忽略 rax.
上半部分的未定义位
4 C 和 C++
C 和 C++ 特别地 不 需要二进制补码二进制有符号整数（C++ std::atomic types). One's complement and sign/magnitude are also allowed 除外，因此 完全 可移植C，这些技巧只对 unsigned 类型有用。显然对于带符号的操作，sign/magnitude 表示中的一组符号位意味着其他位被减去，而不是添加，例如。我没有完成了补语的逻辑
但是，bit-hacks that only work with two's complement are widespread，因为实际上没有人关心其他任何事情。许多与补码一起工作的东西也应该与一个补码一起工作，因为符号位仍然不会改变其他位的解释：它的值只是 -(2N -1)（而不是 2N）。 Sign/magnitude表示没有这个属性: 每一位的位值是正还是负取决于符号位
另请注意，允许 C 编译器假定有符号溢出 永远不会发生 ，因为它是未定义的行为。所以例如compilers can and do assume (x+1) < x is always false. This makes detecting signed overflow rather inconvenient in C. Note that the difference between unsigned wraparound (carry) and signed overflow.
可用于高位垃圾的宽操作：
- 按位逻辑
- 左移（包括
[reg1 + reg2*scale + disp]中的*scale）
- addition/subtraction（因此
LEA 说明：永远不需要地址大小前缀。如果需要，只需使用所需的操作数大小进行截断。）
乘法的低半部分。例如16b x 16b -> 16b 可以用 32b x 32b -> 32b 来完成。您 使用 32 位 imul r32, r/m32, imm32 然后只读取结果的低 16 位。 （不过，如果使用 m32 版本，请注意更宽的内存引用。）
正如 Intel 的 insn ref 手册所指出的，imul 的 2 和 3 操作数形式可以安全地用于无符号整数。输入的符号位不影响 N x N -> N 位乘法结果的 N 位。）
- 2x（即移位 by
x）：至少在 x86 上有效，其中移位计数被屏蔽，而不是饱和，下降到操作的宽度，所以 ecx 中的高位垃圾，甚至 cl 中的高位，都不会影响移位计数。也适用于 BMI2 无标志移位（shlx 等），但不适用于矢量移位（pslld xmm, xmm/m128 等，这会使计数饱和）。 Smart compilers optimize away masking of the shift count, allowing for a safe idiom for rotates in C (no undefined behaviour).
显然像 carry/overflow / sign / zero 这样的标志都会受到更广泛操作的高位垃圾的影响。 x86 的移位将移出的最后一位放入进位标志，因此这甚至会影响移位。
不能与高位垃圾一起使用的操作：
- 右移
全乘法：例如对于 16b x 16b -> 32b，在执行 32b x 32b -> 32b imul 之前，确保输入的高 16 位是零扩展或符号扩展。或者使用一个 16 位的单操作数 mul 或 imul 来不方便地将结果放在 dx:ax 中。 （有符号指令与无符号指令的选择将影响上部 16b，就像在 32b imul 之前进行零或符号扩展一样。）
内存寻址（[rsi + rax]）：根据需要进行符号或零扩展。没有[rsi + eax]寻址模式。
除法余数
- log2（即最高设置位的位置）
- 尾随零计数（除非你知道在你想要的部分某处有一个设置位，或者只是检查一个大于 N 的结果，因为你没有找到检查。）
与无符号基数 2 一样，二进制补码是一个位值系统。无符号 base2 的 MSB 在 N 位数中的位值为 2N-1（例如 231）。在 2 的补码中，MSB 的值为 -2N-1（因此用作符号位）。 The wikipedia article 解释了许多其他理解 2 的补码和取反无符号 base2 数的方法。
关键点是设置符号位不会改变其他位的解释。加法和减法与 unsigned base2 完全相同，只是对结果的解释在 signed 和 unsigned 之间有所不同。 （例如 signed overflow happens when there's a carry into but not out of the sign bit。）
此外，进位仅从 LSB 传播到 MSB（从右到左）。减法也是一样：不管高位有没有借，低位都借。如果这导致溢出或进位，则只有高位会受到影响。例如：
0x801F
-0x9123
-------
0xeefc
低8位，0xFC，不依赖于他们从什么地方借来的。他们 "wrap around" 并将借位传递给高 8 位。
所以加法和减法具有属性结果的低位不依赖于操作数的任何高位
因为 LEA 只使用加法（和左移），所以使用默认的地址大小总是可以的。延迟截断直到操作数大小对结果起作用总是好的。
（例外：16 位代码可以使用地址大小前缀来进行 32 位数学运算。在 32 位或 64 位代码中，地址大小前缀会减小宽度而不是增加宽度。）
乘法可以看作是重复的加法，或者是移位和加法。低半部分不受任何高位影响。在这个 4 位示例中，我写出了所有加起来到低 2 结果位的位积。仅涉及任一源的低 2 位。很明显，这通常有效：部分乘积在加法之前移位，因此源中的高位通常不会影响结果中的低位。
参见Wikipedia for a larger version of this with much more detailed explanation. There are many good google hits for binary signed multiplication，包括一些教学material。
*Warning*: This diagram is probably slightly bogus.
ABCD A has a place value of -2^3 = -8
* abcd a has a place value of -2^3 = -8
------
RRRRrrrr
AAAAABCD * d sign-extended partial products
+ AAAABCD * c
+ AAABCD * b
- AABCD * a (a * A = +2^6, since the negatives cancel)
----------
D*d
^
C*d+D*c
做有符号乘法而不是无符号乘法仍然在低半部分给出相同的结果（本例中的低 4 位）。部分积的符号扩展只发生在结果的上半部分。
这个解释不是很彻底（甚至可能有错误），但是有很好的证据表明在生产代码中使用它是真实和安全的：
gcc 使用 imul 计算两个 unsigned long 输入的 unsigned long 乘积。 See an example of this of gcc taking advantage of LEA for other functions on the Godbolt compiler explorer.
Intel 的 insn ref 手册说：
The two- and three-operand forms may also be used with unsigned
operands because the lower half of the product is the same regardless
if the operands are signed or unsigned. The CF and OF flags, however,
cannot be used to determine if the upper half of the result is
non-zero.
- Intel 的设计决定只引入
imul 的 2 和 3 操作数形式，而不是 mul。
显然，按位二进制逻辑运算 (and/or/xor/not) 独立处理每个位：位位置的结果仅取决于该位位置的输入值。移位也相当明显。
在汇编编程中，想要从寄存器的低位计算一些东西是很常见的，但不能保证其他位都为零。在像 C 这样的高级语言中，您只需将输入转换为小尺寸，让编译器决定是否需要分别将每个输入的高位置零，或者是否可以在事实上。
由于各种原因1，这对于 x86-64（又名 AMD64）尤其常见，其中一些存在于其他 ISA 中。
我将使用 64 位 x86 作为示例，但目的是询问 about/discuss 2's complement and unsigned binary arithmetic in general, since all modern CPUs use it。 （请注意，C 和 C++ 不保证补码 4，并且有符号溢出是未定义的行为。）
例如，考虑一个可以编译为 LEA 指令2 的简单函数。 （在 x86-64 SysV(Linux) ABI3 中，前两个函数参数在 rdi 和 rsi 中， rax 中的 return。int 是 32 位类型。）
; int intfunc(int a, int b) { return a + b*4 + 3; }
intfunc:
lea eax, [edi + esi*4 + 3] ; the obvious choice, but gcc can do better
ret
gcc 知道加法，即使是负符号整数，也只是从右到左进位，所以输入的高位不会影响进入 eax 的内容。因此，it saves an instruction byte and useslea eax, [rdi + rsi*4 + 3]
还有哪些运算的结果低位 属性 不依赖于输入的高位？
为什么它有效？
脚注
1 为什么 x86-64 经常出现这个问题： x86-64 具有可变长度指令，其中额外的前缀字节会改变操作数的大小（从 32 到 64 或 16），因此在以相同速度执行的指令中通常可以节省一个字节。在写入寄存器的低位 8b 或 16b 时（或稍后读取完整寄存器（Intel pre-IvB）时停顿），它也具有错误依赖性（AMD/P4/Silvermont）：出于历史原因，only writes to 32b sub-registers zero the rest of the 64b register .几乎所有算术和逻辑都可以用在通用寄存器的低 8、16 或 32 位以及完整的 64 位上。整数向量指令也相当非正交，某些操作不适用于某些元素大小。
此外，与 x86-32 不同，ABI 在寄存器中传递函数参数，对于窄类型，高位不需要为零。
2 LEA:和其他指令一样，LEA的默认操作数大小是32bit，但是默认地址大小是64位。操作数大小前缀字节（0x66 或 REX.W）可以使输出操作数大小为 16 位或 64 位。地址大小前缀字节 (0x67) 可以将地址大小减少到 32 位（在 64 位模式下）或 16 位（在 32 位模式下）。所以在 64 位模式下，lea eax, [edx+esi] 比 lea eax, [rdx+rsi].
可以做到lea rax, [edx+esi]，但地址仍然只用 32 位计算（进位不会设置 rax 的第 32 位）。使用 lea eax, [rdx+rsi] 可以得到相同的结果，后者少了两个字节。因此，地址大小前缀对 LEA 永远没有用，正如 Agner Fog 出色的 objconv 反汇编程序的反汇编输出中的注释警告的那样。
3 x86 ABI：
调用者 不必 将用于按值传递或 return 较小类型的 64 位寄存器的上半部分归零（或符号扩展）。想要使用 return 值作为数组索引的调用者必须对其进行符号扩展（使用 movzx rax, eax 或 extra-case-for-eax 指令 cdqe。（不是与 cdq 混淆，后者将 eax 符号扩展为 edx:eax，例如设置 idiv。))
这意味着 returning unsigned int 函数可以在 rax 中的 64 位临时值中计算其 return 值，而不需要 mov eax, eax to zero the upper bits 共 rax。这种设计决策在大多数情况下都适用：调用者通常不需要任何额外的指令来忽略 rax.
4 C 和 C++
C 和 C++ 特别地 不 需要二进制补码二进制有符号整数（C++ std::atomic types). One's complement and sign/magnitude are also allowed 除外，因此 完全 可移植C，这些技巧只对 unsigned 类型有用。显然对于带符号的操作，sign/magnitude 表示中的一组符号位意味着其他位被减去，而不是添加，例如。我没有完成了补语的逻辑
但是，bit-hacks that only work with two's complement are widespread，因为实际上没有人关心其他任何事情。许多与补码一起工作的东西也应该与一个补码一起工作，因为符号位仍然不会改变其他位的解释：它的值只是 -(2N -1)（而不是 2N）。 Sign/magnitude表示没有这个属性: 每一位的位值是正还是负取决于符号位
另请注意，允许 C 编译器假定有符号溢出 永远不会发生 ，因为它是未定义的行为。所以例如compilers can and do assume (x+1) < x is always false. This makes detecting signed overflow rather inconvenient in C. Note that the difference between unsigned wraparound (carry) and signed overflow.
可用于高位垃圾的宽操作：
- 按位逻辑
- 左移（包括
[reg1 + reg2*scale + disp]中的*scale） - addition/subtraction（因此
LEA说明：永远不需要地址大小前缀。如果需要，只需使用所需的操作数大小进行截断。） 乘法的低半部分。例如16b x 16b -> 16b 可以用 32b x 32b -> 32b 来完成。您
imul r32, r/m32, imm32然后只读取结果的低 16 位。 （不过，如果使用m32版本，请注意更宽的内存引用。）正如 Intel 的 insn ref 手册所指出的，
imul的 2 和 3 操作数形式可以安全地用于无符号整数。输入的符号位不影响N x N -> N位乘法结果的 N 位。）- 2x（即移位 by
x）：至少在 x86 上有效，其中移位计数被屏蔽，而不是饱和，下降到操作的宽度，所以ecx中的高位垃圾，甚至cl中的高位，都不会影响移位计数。也适用于 BMI2 无标志移位（shlx等），但不适用于矢量移位（pslld xmm, xmm/m128等，这会使计数饱和）。 Smart compilers optimize away masking of the shift count, allowing for a safe idiom for rotates in C (no undefined behaviour).
显然像 carry/overflow / sign / zero 这样的标志都会受到更广泛操作的高位垃圾的影响。 x86 的移位将移出的最后一位放入进位标志，因此这甚至会影响移位。
不能与高位垃圾一起使用的操作：
- 右移
全乘法：例如对于 16b x 16b -> 32b，在执行 32b x 32b -> 32b
imul之前，确保输入的高 16 位是零扩展或符号扩展。或者使用一个 16 位的单操作数mul或imul来不方便地将结果放在dx:ax中。 （有符号指令与无符号指令的选择将影响上部 16b，就像在 32bimul之前进行零或符号扩展一样。）内存寻址（
[rsi + rax]）：根据需要进行符号或零扩展。没有[rsi + eax]寻址模式。除法余数
- log2（即最高设置位的位置）
- 尾随零计数（除非你知道在你想要的部分某处有一个设置位，或者只是检查一个大于 N 的结果，因为你没有找到检查。）
与无符号基数 2 一样，二进制补码是一个位值系统。无符号 base2 的 MSB 在 N 位数中的位值为 2N-1（例如 231）。在 2 的补码中，MSB 的值为 -2N-1（因此用作符号位）。 The wikipedia article 解释了许多其他理解 2 的补码和取反无符号 base2 数的方法。
关键点是设置符号位不会改变其他位的解释。加法和减法与 unsigned base2 完全相同，只是对结果的解释在 signed 和 unsigned 之间有所不同。 （例如 signed overflow happens when there's a carry into but not out of the sign bit。）
此外，进位仅从 LSB 传播到 MSB（从右到左）。减法也是一样：不管高位有没有借，低位都借。如果这导致溢出或进位，则只有高位会受到影响。例如：
0x801F
-0x9123
-------
0xeefc
低8位，0xFC，不依赖于他们从什么地方借来的。他们 "wrap around" 并将借位传递给高 8 位。
所以加法和减法具有属性结果的低位不依赖于操作数的任何高位
因为 LEA 只使用加法（和左移），所以使用默认的地址大小总是可以的。延迟截断直到操作数大小对结果起作用总是好的。
（例外：16 位代码可以使用地址大小前缀来进行 32 位数学运算。在 32 位或 64 位代码中，地址大小前缀会减小宽度而不是增加宽度。）
乘法可以看作是重复的加法，或者是移位和加法。低半部分不受任何高位影响。在这个 4 位示例中，我写出了所有加起来到低 2 结果位的位积。仅涉及任一源的低 2 位。很明显，这通常有效：部分乘积在加法之前移位，因此源中的高位通常不会影响结果中的低位。
参见Wikipedia for a larger version of this with much more detailed explanation. There are many good google hits for binary signed multiplication，包括一些教学material。
*Warning*: This diagram is probably slightly bogus.
ABCD A has a place value of -2^3 = -8
* abcd a has a place value of -2^3 = -8
------
RRRRrrrr
AAAAABCD * d sign-extended partial products
+ AAAABCD * c
+ AAABCD * b
- AABCD * a (a * A = +2^6, since the negatives cancel)
----------
D*d
^
C*d+D*c
做有符号乘法而不是无符号乘法仍然在低半部分给出相同的结果（本例中的低 4 位）。部分积的符号扩展只发生在结果的上半部分。
这个解释不是很彻底（甚至可能有错误），但是有很好的证据表明在生产代码中使用它是真实和安全的：
gcc 使用
imul计算两个unsigned long输入的unsigned long乘积。 See an example of this of gcc taking advantage of LEA for other functions on the Godbolt compiler explorer.Intel 的 insn ref 手册说：
The two- and three-operand forms may also be used with unsigned operands because the lower half of the product is the same regardless if the operands are signed or unsigned. The CF and OF flags, however, cannot be used to determine if the upper half of the result is non-zero.
- Intel 的设计决定只引入
imul的 2 和 3 操作数形式，而不是mul。
显然，按位二进制逻辑运算 (and/or/xor/not) 独立处理每个位：位位置的结果仅取决于该位位置的输入值。移位也相当明显。