高校问答fob乐队:利用汇编语言写出高效的3x+1程序
来源：百度文库 编辑：高校问答 时间：2024/04/29 12:34:36
我们就把它乘3再加上1。在这样一个变换下，我们就得到了一个新的
自然数。如果反复使用这个变换，我们就会得到一串自然数。是否对于所有自然数，这一串生成的序列都会陷入4-2-1的循环中呢？这就是3x+1问题。
现在我要编写一个解决这个问题的程序，其中的核心部分就是用汇编把这个东西表达出来。待运算数有64bit，高位放在ebx，低位放在eax。si和di分别记录总步数和奇变换的数目。
请先进行一定的思考再回答，请不要做出类似“好难啊”这样的回答。多谢合作！
注意：至少要比以下的程序效率高：
start6:
__asm test ax, 1
__asm jz evenpre6
//oddpre6
__asm test ax, 2
__asm jz res126
//res36:
__asm add di, 2
__asm add si, 4
__asm mov ecx, eax
__asm mov edx, ebx
__asm shl eax, 1
__asm rcl ebx, 1
__asm inc eax
__asm shrd ecx, edx, 2
__asm shr edx, 2
__asm stc
__asm adc eax, ecx
__asm adc ebx, edx
__asm jmp start6
evenpre6:
__asm test ax, 2
__asm jnz res126
//res06:
__asm add si, 2
__asm shrd eax, ebx, 2
__asm shr ebx, 2
__asm jmp start6
res126:
__asm add si, 3
__asm inc di
__asm mov ecx, eax
__asm mov edx, ebx
__asm shrd ecx, ebx, 2
__asm shr edx, 2
__asm sub eax,ecx
__asm sbb ebx, edx
__asm jmp start6
允许MMX,SSE,SSE2代码。
请考虑乱序执行的问题。
isjk 与 懒虫007 ，你们的编写方法我也尝试过，但是都比我上面写的算法效率要低。不管怎么样，还是谢谢你们的关注了！
爱因景润，这个方法就是本来我采用的方法，后来我用跳步看的方法效率就提高了，你可以数一下所需的指令数。还有，我代码里本来有判断为1和溢出的，但是我删掉了，很容易加上去的。谢谢你的关注！
我的邮箱：fwjmath<arobase>gmail.com
unsigned long d;
__asm
{
mov di,0
mov si,0
start: cmp eax,1
jnz go_on
cmp ebx,0
jnz go_on
jmp over
go_on: test ax,1
jz c1// 偶数跳
mov d,eax
mov edx,ebx
mov cx,2
xxx: stc
add eax,d
adc ebx,edx
loop xxx
stc
add eax,1
adc ebx,0
inc di// 记录奇变幻次数
inc si
jmp start
c1: shrd eax, ebx, 1
shr ebx, 1
inc si
jmp start
over:
}
这个程序我调试过了，只要运算过程中不出现越界就没问题。变量d你定义到数据段中就行了。
另外我还调试了一下你给的代码，好像无论怎样都jmp start6，根本跳不出来耶。
还有据我理解，你的代码是往前看好几步，然后2个4个的往上加，我不知道你为什么采用这种算法，而不是1个1个地加。
呵呵，用C语言做，然后把个好编译器编译，最好再把编译的东西反编译成汇编就OK了
while(n){
if(n%2==0)
{
m=n\2;
else{
m=n*3+1
}
}
}
注意：至少要比以下的程序效率高：
start6:
__asm test ax, 1
__asm jz evenpre6
//oddpre6
__asm test ax, 2
__asm jz res126
//res36:
__asm add di, 2
__asm add si, 4
__asm mov ecx, eax
__asm mov edx, ebx
__asm shl eax, 1
__asm rcl ebx, 1
__asm inc eax
__asm shrd ecx, edx, 2
__asm shr edx, 2
__asm stc
__asm adc eax, ecx
__asm adc ebx, edx
__asm jmp start6
evenpre6:
__asm test ax, 2
__asm jnz res126
//res06:
__asm add si, 2
__asm shrd eax, ebx, 2
__asm shr ebx, 2
__asm jmp start6
res126:
__asm add si, 3
__asm inc di
__asm mov ecx, eax
__asm mov edx, ebx
__asm shrd ecx, ebx, 2
__asm shr edx, 2
__asm sub eax,ecx
__asm sbb ebx, edx
__asm jmp start6
容我再想想 现在读完你的程序 觉得就是有点问题 太繁了点吧 你把 邮件地址放下 我回头发给你吧
暂时想不出什么更高的，但肯定比编译器效率高很多。