selph
selph
发布于 2022-03-27 / 282 阅读
0
0

《xchg rax,rax》片段分析0x1f--Collatz序列

前言

本次是该系列的的第0x1f篇,本篇介绍了巧用汇编指令bsf,来计算Collatz序列


实验环境:

  • Windows10 + VS2022 + masm

0x1f

代码片段链接:xorpd | xchg rax,rax 0x1f

.loop:
    bsf      rcx,rax
    shr      rax,cl
    cmp      rax,1
    je       .exit_loop
    lea      rax,[rax + 2*rax + 1]
    jmp      .loop
.exit_loop:

代码分析

bsf指令介绍

bsf:bit scan forware,顺向位扫描(从右往左扫描),找到第一个1的位置

例如最后是1000(2),则输出3

代码分析

测试代码:

.code
main proc
    mov     rcx, 02100h
    mov     rax, 011h

loop1:
    bsf      rcx,rax   ; 位扫描,从右往左扫描,找到第一个1的位置,如果最后是1000(2),则输出3 
    shr      rax,cl    ; rax右移cl次,就是让rax右移,直到末尾是1
    cmp      rax,1     ; 判断rax是否为1
    je       exit_loop ; 为1,则跳转 
    lea      rax,[rax + 2*rax + 1] ; 不为1,则取地址[rax + 2*rax + 1]
    jmp      loop1     ; 循环
exit_loop:

	ret

main ENDP
END

这是求解经典的3n+1问题的计算过程(也是Collatz序列,考拉咨猜想)

输入一个数n,如果是偶数,则n=n/2,如果是奇数则n=3*n+1,并输出(只不过这里没输出,不过可以自己加上)

参考资料


评论