求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. }
   
9. 
   
10. int GreaterEqualBit2_c(int n)
    
11. {
    
12. int k1,k2;
    
13. int n2;
    
14. if (n<7)
    
15. return n;
    
16. 
    
17. if ( !(n & (n-1)) )
    
18. return n;
    
19. 
    
20. k1=log2(n);
    
21. n2=n- (1 << k1);
    
22. 
    
23. k2=log2(n2);
    
24. if ( n2== (1<<k2) )
    
25. return n;
    
26. 
    
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]
   
8. 
   
9. cmp eax,7
   
10. jl tExit
    
11. 
    
12.   
    
13. bsr ecx,eax //ecx: k1
    
14. mov edx,1
    
15. shl edx,cl //edx: 1 << k1
    
16. 
    
17. mov ebx,eax
    
18. sub ebx,edx // ebx: n2 = n- (1<<k1);
    
19. jz    tExit
    
20. 
    
21. bsr ecx,ebx // ecx: k2
    
22. 
    
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
    
29. 
    
30. lea eax,  [edx + ebx*2]   //eax: (1<<k1) +  2* (1 << k2)
    
31. 
    
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?