检查数字是否为偶数

Question

我正在研究 low level bit hacks，我想为每个程序编写一个汇编程序。这是我用来检查数字是否为偶数的内容：

is_even:
    # check if an integer is even. 
    # This is the same as seeing if its a multiple of two, i.e., & 1<<n - 1
    # rdi stores the number
    xor %eax, %eax
    test [=10=]b1, %rdi
    setz %al
    ret

_start:
    mov , %rdi
    call is_even

是否有任何方法可以改进以上内容或使其更具可读性？是否可以用 2 条指令而不是 3 条指令进行 is_even 检查，因为第一个 xor 和第二个 setz 似乎可能会转换为一个指令。

Answer 1

我无法将其简化为两条指令，但我可以将其打得更短一些。

您当前的版本是 12 个字节，包括 ret。您可以改用 test , %dil 削减两个字节，因为输入的高字节无关紧要，因此将 4 字节立即数换成 1 字节立即数和前缀字节。这样可以减少到 10。

您可以利用移位指令移入进位标志这一有点晦涩的事实，然后执行

，从而再减少两个字节

is_even: // 8 bytes
    xor %eax, %eax
    shr , %edi
    setnc %al
    ret

gcc 和 clang both do

is_even: // 8 bytes
    mov %edi, %eax
    not %eax
    and , %eax
    ret

少一个字节，

is_even: // 7 bytes
    shr , %edi
    sbb %eax, %eax
    inc %eax
    ret

sbb 是“借用减法”，即从一个寄存器中减去另一个寄存器，如果设置了进位标志，则再减去 1。如果输入为偶数，则为 0，如果为奇数，则为 -1。然后加 1 让我们到达我们想要的位置。这可能会更慢，因为我不确定 CPU 是否知道结果不依赖于 %eax.

的先前值

不过，我看不出有什么方法可以简化为两条指令。这是条件 setcc 指令的一个烦人的特性，它们只设置低字节并单独保留寄存器的其余部分，在您希望完整寄存器中的布尔值的常见情况下，迫使您自己将其归零。而且我们必须在两个不同的寄存器中获取输入和输出，这很尴尬，因为 x86 的模型输出寄存器始终是输入之一。

Answer 2

TL:DR：加 1 翻转低位，保证，所以你可以使用 lea/and。见下文。

您选择编写一个 return 是一个布尔整数的完整函数，而不是仅仅创建一个 FLAGS 条件（这是大多数代码需要的：test , %dil 并且您已经完成；分支或 cmov或 setnz 或 setz 或任何你真正想做的基于一个值是偶数）。

如果你要 return 一个整数，那么你实际上不需要将条件放入 FLAGS 中然后退出，特别是如果你想要一个“宽”return 值。 x86 setcc 只写低字节是一个不方便的设计，大多数时候你想要创建一个更宽的 0 / 1 整数需要额外的 xor-zeroing 指令。（我希望 AMD64 已经整理了设计并将 64 位模式的操作码的含义更改为 setcc r/m32 但他们没有。）

您选择了 return 1 函数的语义；这与低位的值相反。（即 return (~x)&1;）您还选择使用 x86-64 System V 调用约定创建一个函数，从调用约定中强加开销，在与您传入的寄存器不同的寄存器中获取 arg。

这个函数显然太琐碎了，不值得 call/return 开销；在现实生活中，您只需将其内联并优化到调用者中即可。因此将其优化为stand-alone函数主要是一项愚蠢的练习，除了在不破坏原始寄存器的情况下在单独的寄存器中获取 0/1 的想法。

如果我在 https://codegolf.stackexchange.com/, I'd follow this code-golf tip 上写一个答案并选择我的调用约定在 EAX 中传递一个 arg 并且 return 在 AL 中传递一个布尔值（就像 gcc -m32 -mregparm=3 会）。或者 return ZF 中的 FLAGS 条件。或者，如果允许，请选择我的 return 语义，这样 AL=0 表示偶数，AL=1 表示奇数。然后

# gcc 32-bit regparm calling convention
is_even:          # input in RAX, bool return value in AL
    not   %eax             # 2 bytes
    and   , %al          # 2 bytes
    ret

# custom calling convention:
is_even:   # input in RDI
           # returns in ZF.  ZF=1 means even
    test  , %dil         # 4 bytes.  Would be 2 for AL, 3 for DL or CL (or BL)
    ret

2条指令不破坏输入

is_even:
    lea   1(%rdi), %eax          # flip the low bit
    and   , %eax               # and isolate
    ret

异或不带进位相加。当carry-in为零时（保证低位，ADC除外），给定位的结果相同用于异或和加法。检查 1 位“half adder”（无进位）的 table / gate-equivalent 的真实性：“和”输出实际上只是 XOR，进位输出只是 AND。

(XOR 与 1 翻转一点，与 NOT 相同。)

在这种情况下，我们不关心 carry-out 或任何高位（因为我们即将用 & 1 核对那些位是相同的操作），所以我们可以使用 LEA 作为 copy-and-add 来翻转低位。

使用 XOR 而不是 ADD 或 SUB 对 SIMD 很有用，其中 pxor 可以运行在更多端口上比 paddb 或 psubb 在 Skylake 之前的 CPU 上。当你想 range-shift unsigned 到 signed for pcmpgtb 什么的时候，你想添加 -128，但这和翻转每个字节的高位是一样的。

您可以使用它翻转更高的位，例如lea 8(%rdi), %eax 将翻转 1<<3 位位置（并可能进位到所有更高位）。我们知道那个位的carry-in会是0，因为x + 0没有进位，8的低3位全为0。

（这个想法是后来https://catonmat.net/low-level-bit-hacks中一些更有趣的bit-hacks的核心）

检查数字是否为偶数

Check if a number is even

x86

assembly

bit-manipulation

x86-64

2条指令不破坏输入