首页 文章

程序集中的平方根，如何移位和更改位

提问于
浏览 次
0

我想在汇编中编写一个快速整数平方根算法，它采用无符号32位 . 我一直在阅读this，并得到了一个主意 . 这是我的伪代码：

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

我想要使用除法或sqrt指令 . 我知道我应该使用 shr ，但我不知道从哪里开始或怎么做 . 如何在for循环中执行操作？我从哪里开始？

assembly sqrt

1 回答

  • 2

    （英特尔语法，自行转换为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.当你想要将值从/转换为字符串时，所有转换事件都会发生，但只要你用值计算，它就在那里所有形式的登记册同时存在 . 这取决于你如何看待寄存器 . 在源代码中使用hexa / decimal / binary是这样的，编写数字的STRING表示，它由汇编程序转换为值本身 .

    二进制表示是特殊的，因为CPU可以处理特定位（使用和/ xor /或，旋转，位测试/设置等），因为它具有“导线”类型中的那些值，并且它是它的本机表示 . 这就像当人类在计算“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 counter to bit mask（或者使用一些我不知道的位设置/重置指令，因为几乎从不需要它们） .

    但是如果你研究我的代码，你会看到有直接的快捷方式来处理位掩码本身，而不计算"i-th bit"部分，使代码更短更快（虽然我可能通过push / pop杀死它，也许再使用一个寄存器像 esi 来存储值会更好...然后再次演示如何使用堆栈，以及标志如何不受某些指令的影响，这样你可以推迟使用 cmp 结果，如果你小心不修改所需的旗帜） .

    回复于

相关问题