装配中的平方根,如何移位和更改位

安德鲁

我想在汇编中编写一个快速的整数平方根算法,它需要无符号的32位。我一直在阅读过,并有了一个主意。这是我的伪代码:

res <- 0
for i from 15 downto 0 do:
   change the ith bit of result to 1
   if res^2 > x then:
      change the ith bit of res back to 0
return res

到目前为止,我已经做完了:

sqrt:
  movl $0, %eax
  movl $15, %edx
  jmp .L8
.L9

.L8
  cmpq cmpq $0, %edx
  jge .L9

我陷于for循环操作中,更改了ith位并进行了移位。我也不想使用除法或sqrt指令。我知道我应该使用shr,但是我不知道从哪里开始或如何做。我该如何在for循环中进行操作?我从哪里开始?

踏板7g

(Intel语法,自行转换为AT&T)

    mov   ebx,<number> ; *number* to find sqrt of
    mov   ecx,0x8000   ; bitmask (starting with b15 bit set)
    ;^^^ 0x8000 = decimal 32768 = binary 1000 0000 0000 0000
    xor   eax,eax      ; result <- 0
sqrt_loop:
    xor   eax,ecx      ; set bit in eax
    push  eax          ; store result (will be destroyed by mul)
    mul   eax          ; edx:eax <- eax*eax (ignoring edx next)
    cmp   eax,ebx      ; compare with *number*
    pop   eax          ; restore result
    jbe   keep_bit     ; res^2 <= *number* -> bit stays set
    xor   eax,ecx      ; unset bit in eax
keep_bit:
    shr   ecx,1        ; next bit
    jnz   sqrt_loop    ; loop till all bits are tried

(我没有尝试过+对其进行调试,因此可能存在一些错误。但是我认为,与您的伪算法以及通过调试重写到AT&T一起,这应该足以使您入门。)

正如玛格丽特指出的那样,数字就是数字,这就是价值。因此0x8000已经在CPU导线中编码为b15设置为1,其他位设置为0。当您想将值从字符串转换为字符串时,所有的转换工作都会发生,但是只要您使用值进行计算,它就会存在同时以各种形式注册。这取决于您如何看待寄存器。在源代码中使用十六进制/十进制/二进制是这样的:编写数字的STRING表示形式,汇编程序将其转换为值本身。

二进制表示形式是特殊的,因为CPU可以寻址特定的位(具有和/或,和,或旋转,位测试/设置等),因为它具有那些值在“电线”中,并且是其本机表示形式。就像人类在计算“ 10 * 3456”时在“作弊”,最后只写额外的0以获得结果一样,因为十进制格式就是10 *的特殊之处。对于CPU,位操作和2的各种幂运算也会发生同样的情况。但是十进制技巧是不可能的,因为它们有CPU以正确的方式进行计算,实数乘以10。

无论如何,当您只有位数时,并且想要获取位掩码本身,例如如何从15中获取0x8000:

mov   ecx,15  ; i-th bit
mov   eax,1   ; set b0 (lowest bit)
shl   eax,cl  ; shift all bits (all zeroed + b0 set) cl-many times left
; eax now contains 0x8000 = b15 set, other bits zeroed

因此,如果您坚持使用算法的方法,则每次都必须重新计算for计数器到位掩码(或使用一些位设置/重置指令,我从头开始并不知道,因为几乎不需要它们)。

但是,如果您研究我的代码,您会发现有直接的快捷方式可以在位掩码本身上工作,而无需计算“第i个位”部分,从而使代码更短,更快(尽管我可能是通过push / pop杀死了它,也许再使用一个寄存器esi来存储值会更好一些...然后再次说明如何使用堆栈,以及标志如何不受某些指令的影响,因此cmp如果您谨慎的话,可以推迟使用结果以不修改所需的标志)。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档