《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，并输出（只不过这里没输出，不过可以自己加上）

参考资料

• [intel bsf指令_brucexu1978的博客-CSDN博客_bsf指令](https://blog.csdn.net/brucexu1978/article/details/6328411#:~:text=intel汇编指令：bsf oprd1%2Coprd2%3B 顺向位扫描,(bit scan forward) 从右向左（从位0-->位15或位31）扫描字或双字操作数oprd2中第一个含"1"的位，并把扫描到的第一个含'1'的位的位号送操作数oprd1)
• BSF — Bit Scan Forward (felixcloutier.com)