; this is practicaly the SAR instruction,
; the mask for the absolute value is
; number >> (sizeof(short)) * CHAR_BIT -1)
; number >> (2 * 8) - 1 = 15
; so normaly we would do SAR bx, 15 and done
mov bl, ah ; BX = AX>>8
add bx, bx ; BX <<= 1
neg bh ; 0 or -1
mov bl, bh ; duplicate the full BX
mov cx, ax ;
add cx, bx ; the number + mask
xor bx, cx ; (number+mask) ^ mask
2条答案
按热度按时间qlzsbp2j1#
愚蠢的想法#1:在16位真实的模式下,这是不可能的。即使一个表的整个64 kiB段是不够的;我们需要两倍的时间来查找任何可能的16位值的2字节结果。
我们可以很容易地用32位寻址,比如
xor ebx, ebx
/mov bx, ax
/mov bx, [table + ebx*2]
,如果你能调整128 kiB的表数据。:P完全在规则内,你可以用
sub esp, 1<<17
在32位或64位模式下在堆栈上构造表,并用mov word [esp+0], 0
/mov word [esp + 2], 1
/etc存储数据。完全展开,没有循环,所以大约有256 kiB的机器代码。但是,这在真实的模式下不起作用,完全是效率的笑话。我们可以使用x86部分寄存器技巧将符号位隔离为0 / 1整数:
字符串
或者最后3条指令可以优化为2条
型
头奖;我们有一个
sar ax,15
或cwd
值,它的所有位都是0或1,广播AX的符号位,准备与2的补码标识(How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results?)一起使用,就像编译器使用(https://godbolt.org/z/n3yoUp)一样。通常,您可以使用
xor ax, dx
/sub ax, dx
来修改原始值。我之前认为这个挑战要求你避免修改任何 * 其他 * 寄存器,否则保持AX不变的限制是微不足道的,不值得成为挑战的一部分。但是我认为如果没有内存中的额外暂存空间或另一个寄存器,这是不可能的。编辑澄清了没有必要。
型
与
-1
的异或像NOT一样翻转所有位。与0
的异或是一个空操作。带
-1
的整数递增1,带0
的整数是空操作(0
是加法和异或的单位元素)。所以这有条件地应用了2的补码
-x = ~x + 1
恒等式。附言:我花了几分钟的时间来思考这个问题,排除了任何全寄存器方法,我非常熟悉x86和位操作,例如用x86机器码编写codegolf.SE答案,并用SIMD做一些重要的事情。IMO这是一个有趣的挑战。
此外,在真实的生活中,您永远不会想编写这样的代码;
cwd
或cdq
要高效得多,或者对于AX、copy和sar
以外的源代码,部分寄存器的东西甚至会导致某些乱序执行CPU(如Intel PPro到Nehalem)的停顿。例如,在此源的the Godbolt compiler explorer上:
型
使用无符号返回值可以避免最负的2的补码整数的有符号整数溢出未定义行为。(
-INT_MIN
是未定义的行为)。我认为我写它的方式实际上依赖于C实现是2的补码,虽然,因为0U - x
将x
转换为无符号,以匹配另一边 *,然后 * 将其用作二进制-
的操作数。或者这就是我们想要的,对于无符号0U-x
,从0x8000
的输入生成0x8000
(对于16位int)。GCC这样做是为了设置EAX = abs(EDI)(x86-64 System V调用约定)。
型
clang针对x86-64执行此操作,使用从NEG读取标志的条件移动:
型
在某些CPU上,这样做会更有效:
型
Sandybridge消除了xor-zeroing,但没有mov,对于不执行
mov
消除的CPU,这缩短了关键路径。mov eax,edi
在关键路径上,但xor
-zeroing不是。或者我们可以执行mov eax, edi
/neg edi
/cmovnl eax, edi
以再次允许MOV和NEG并行运行。CMOV是Broadwell之前的Intel CPU上的2-uop指令。(CMOVA和CMOVBE在当前Intel上仍然是2 uop,因为它们读取CF * 和 * ZF,它们在不同的组中分别重命名。其他是1 uop)
apeeds0o2#
感谢Peter Cordes的回答,代码很简单,问题是SAR指令,但是Peter创建得很好。
号码已加载到AX中
字符串
现在答案在BX中,AX没有被更改