我们学校有一个问题,是给那些想测试自己的学生的。我花了很长时间在这个问题上,但还是想不出来。AX寄存器中有一个16位的数字,这个数字是有符号的。得到它的绝对值,AX中的数字必须保持不变(EDIT:没有限制的寄存器数量,AX寄存器可以改变,但在函数结束时,它需要是原始的数字),答案应该是BX。你只能使用这些指令:MOV、ADD、XOR、NOT、AND、OR、NEG。像编译器那样处理SAR是很容易的,但是如果没有它,就不清楚如何在符号位上获得任何行为条件。
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的机器代码。但是,这在真实的模式下不起作用,完全是效率的笑话。
xor ebx, ebx
mov bx, ax
mov bx, [table + ebx*2]
sub esp, 1<<17
mov word [esp+0], 0
mov word [esp + 2], 1
我们可以使用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
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
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或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不变的限制是微不足道的,不值得成为挑战的一部分。但是我认为如果没有内存中的额外暂存空间或另一个寄存器,这是不可能的。编辑澄清了没有必要。
sar ax,15
cwd
xor ax, dx
sub ax, dx
mov bx, ax xor bx, dx ; ~x or x sub bx, dx ; ~x + 1 or x
xor bx, dx ; ~x or x
sub bx, dx ; ~x + 1 or x
型与-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上:
-1
0
-x = ~x + 1
cdq
sar
unsigned absval(int x) { return x<0 ? 0U - x : x;}
unsigned absval(int x) {
return x<0 ? 0U - x : x;
}
型使用无符号返回值可以避免最负的2的补码整数的有符号整数溢出未定义行为。(-INT_MIN是未定义的行为)。我认为我写它的方式实际上依赖于C实现是2的补码,虽然,因为0U - x将x转换为无符号,以匹配另一边 *,然后 * 将其用作二进制-的操作数。或者这就是我们想要的,对于无符号0U-x,从0x8000的输入生成0x8000(对于16位int)。GCC这样做是为了设置EAX = abs(EDI)(x86-64 System V调用约定)。
-INT_MIN
0U - x
x
-
0U-x
0x8000
mov eax, edi cdq ; sign-extend EAX into EDX:EAX xor eax, edx sub eax, edx ret
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
neg eax ; 0 - x
cmovl eax, edi ; copy the original if 0 was < x
型在某些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
; shorter critical path on CPUs where mov is not zero latency
xor eax, eax
sub eax, edi ; 0 - x
型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)
mov
mov eax,edi
xor
neg edi
cmovnl eax, edi
apeeds0o2#
感谢Peter Cordes的回答,代码很简单,问题是SAR指令,但是Peter创建得很好。号码已加载到AX中
; 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 donemov bl, ah ; BX = AX>>8add bx, bx ; BX <<= 1neg bh ; 0 or -1 mov bl, bh ; duplicate the full BXmov cx, ax ;add cx, bx ; the number + mask xor bx, cx ; (number+mask) ^ mask
; 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
字符串现在答案在BX中,AX没有被更改
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没有被更改