愚蠢的想法#1:查找表。这不能在 16 位实模式下工作。即使对于一个表来说整个 64kiB 段也是不够的;我们需要两倍的时间才能在 2 字节结果中查找任何可能的 16 位值。
我们可以通过 32 位寻址轻松做到这一点,例如xor ebx, ebx
/ mov bx, ax
/ mov bx, [table + ebx*2]
,如果您可以证明 128kiB 的表数据合理。 :P
完全在规则范围内,您可以在 32 位或 64 位模式下在堆栈上构造表sub esp, 1<<17
并将数据存储为mov word [esp+0], 0
/ mov word [esp + 2], 1
/ 等。完全展开,无循环,因此大约有 256kiB 的机器代码。但同样,这在实模式下不起作用,而且对效率来说完全是个笑话。
我们可以使用 x86 部分寄存器恶作剧将符号位隔离为 0 / 1 整数:
xor dx, dx ; DX = 0
mov dl, ah ; DX = AX>>8 (zero extended)
add dx, dx ; DX <<= 1 shifts the sign bit alone into DH
mov dl, dh
mov dh, 0 ; DX = (AX<0) = sign bit of AX zero extended to 16-bit
neg dx ; DX = 0 or -1
或者最后3条指令可以优化为2条
neg dh ; 0 or -1 according to sign bit of AX
mov dl, dh ; duplicate to the full DX = 0 or -1
大奖;我们有我们的sar ax,15
or cwd
具有所有位 0 或所有位 1 的值,广播 AX 的符号位,准备与 2 的补码标识一起使用 (如何证明 C 语句 -x、~x+1 和 ~(x-1) 产生相同的结果? https://stackoverflow.com/questions/2278518/how-to-prove-that-the-c-statement-x-x1-and-x-1-yield-the-same-results) 就像编译器使用 (https://godbolt.org/z/n3yoUp https://godbolt.org/z/n3yoUp).
通常你会使用xor ax, dx
/ sub ax, dx
来修改原始值。
我之前认为这个挑战要求你避免修改任何other寄存器,否则对 AX 不修改的限制是微不足道的,不值得作为挑战的一部分。但我认为如果内存或其他寄存器中没有额外的暂存空间,这是不可能的。编辑澄清说没有必要这样做。
mov bx, ax
xor bx, dx ; ~x or x
sub bx, dx ; ~x + 1 or x
异或与-1
像 NOT 一样翻转所有位。异或与0
是一个空操作。
子带-1
增加 1,SUB 与0
是一个空操作。 (0
是加法和异或的单位元。)
所以这有条件地应用 2 的补码-x = ~x + 1
身份。
PS:我花了几分钟的时间思考这个问题,排除了任何全注册方法,我very熟悉 x86 并且非常熟悉位操作,例如用 x86 机器代码编写 codegolf.SE 答案,并使用 SIMD 做一些重要的事情。在我看来,这是一个有趣的艰巨挑战。
而且,您永远不会想在现实生活中编写这样的代码;cwd
or cdq
效率更高,或者对于 AX 之外的源寄存器,复制和sar
。部分寄存器的内容甚至会导致某些乱序执行 CPU(例如 Intel PPro 通过 Nehalem)停顿。
例如,关于Godbolt 编译器浏览器 https://godbolt.org/z/cHkXdo对于这个来源:
unsigned absval(int x) {
return x<0 ? 0U - x : x;
}
使用无符号返回值可以让我们避免最负 2 的补码整数的有符号整数溢出未定义行为。 (-INT_MIN
是未定义的行为)。我认为我编写它的方式实际上依赖于 C 实现是 2 的补码,因为0U - x
皈依者x
未签名以匹配另一方before使用它作为二进制的操作数-
。或者也许这就是我们想要的,对于未签名的0U-x
生产0x8000
从输入0x8000
(对于 16 位整数)。
GCC 这样做是为了设置 EAX = abs(EDI)(x86-64 System V 调用约定)。
mov eax, edi
cdq ; sign-extend EAX into EDX:EAX
xor eax, edx
sub eax, edx
ret
clang 对 x86-64 执行此操作,使用从 NEG 读取标志的条件移动:
mov eax, edi
neg eax ; 0 - x
cmovl eax, edi ; copy the original if 0 was < x
ret
在某些 CPU 上这样做会更高效:
; shorter critical path on CPUs where mov is not zero latency
xor eax, eax
sub eax, edi ; 0 - x
cmovl eax, edi ; copy the original if 0 was < x
ret
Sandybridge 消除了异或归零,但没有消除 mov,对于不这样做的 CPUmov
消除这缩短了关键路径。mov eax,edi
处于关键路径上,但是xor
-归零不是。或者我们可以这样做mov eax, edi
/ neg edi
/ cmovnl eax, edi
再次允许 MOV 和 NEG 并行运行。
CMOV 是 Broadwell 之前的 Intel CPU 上的 2 uop 指令。 (CMOVA 和 CMOVBE 在当前的 Intel 上仍然是 2 uops,因为它们读取 CFandZF,在不同组中分别更名。其他都是1 uop)