求bit位为1数目不超出2的正整数

无心人

错了 jz 呵呵

liangbch

我的 C + 汇编的版本

1. int log2(int n)
2. {
3. _asm
4. {
5. mov ecx,n
6. bsr eax,ecx
7. }
8. }
10. int GreaterEqualBit2_c(int n)
11. {
12. int k1,k2;
13. int n2;
14. if (n<7)
15. return n;
17. if ( !(n & (n-1)) )
18. return n;
20. k1=log2(n);
21. n2=n- (1 << k1);
23. k2=log2(n2);
24. if ( n2== (1<<k2) )
25. return n;
27. return (1<<k1) + ( 1 << (k2+1) );
28. }

复制代码

无心人

你这叫哪门子代码啊

liangbch

下面是完全使用汇编的版本，共22条指令。 稍作修改，改为20条指令

1. _declspec(naked)
2. int GreaterEqualBit2_asm(int n)
3. {
4. __asm
5. {
6. push ebx
7. mov eax, dword ptr[esp + 4+ 4]
9. cmp eax,7
10. jl tExit
13. bsr ecx,eax //ecx: k1
14. mov edx,1
15. shl edx,cl //edx: 1 << k1
17. mov ebx,eax
18. sub ebx,edx // ebx: n2 = n- (1<<k1);
19. jz tExit
21. bsr ecx,ebx // ecx: k2
23. push ebx // save n2
24. mov ebx,1
25. shl ebx,cl // ebx: (1 << k2)
26. pop ecx // ecx: n2
27. cmp ecx,ebx
28. jz tExit // n2 == 1<<k2
30. lea eax, [edx + ebx*2] //eax: (1<<k1) + 2* (1 << k2)
32. tExit:
33. pop ebx
34. ret
35. }
36. }

复制代码

无心人

找到了另外的一个写法 mov eax, n mov edx, eax bsr ecx, edx btr edx, ecx bsr ecx, edx jz exit btr edx, ecx cmp edx, 0 je exit mov edx, 1 shl edx, cl sub edx, 1 or eax, edx add eax, 1 exit:

无心人

这个代码 连ret一共15条 位指令只用四个 其他均为简单指令

无心人

不知道17#和25#哪个快 似乎17#也能照25#的再优化下

gxqcn

我自己写了个纯汇编版本， 仅15条指令的（包含最后的ret指令）， 且不含任何jump指令。 暂不贴出来；待进一步优化后再公开。 大家继续。。。

无心人

不含任何jump指令？？ ======================= 又是利用了CF？ 哎 要费脑子猜测了

无心人

可能还利用了cmovcc?