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

shshsh_0510

说明一下，表中对8个位中有两个1的数据，预先存好返回值，这样先检测前8位，只有9/256的数据需要继续检测后面
如果有一个1，也存好相应值
由于预先算好，于是程序执行主要是寻址

shshsh_0510

原帖由 无心人 于 2009-2-3 17:08 发表


   你认为这么复杂的代码比我的汇编要高效么？
   况且，最终的代码的适用范围要比GxQ题目要求的大
   只要是1-2^32-2就可以

效率和代码复杂性的关系是这样的么？

shshsh_0510

可能是比不过你们的，毕竟用内存和寄存器是有较大差别的，不好说，我觉得这个得试试

无心人

从翻译后的汇编语句的行数就肯定要比我的多很多了啊
而且这么多比较和分支

shshsh_0510

试了一下，比你们的慢10倍

无心人

   那个，你比较了时间， 哪组汇编快？？？

gxqcn

1. typedef unsigned int UINT32;
   
2. 
   
3. const UINT32 POW2[] = { 0, 1UL, 1UL<<1, 1UL<<2, 1UL<<3,
   
4.                         1UL<<4,  1UL<<5,  1UL<<6,  1UL<<7,
   
5.                         1UL<<8,  1UL<<9,  1UL<<10, 1UL<<11,
   
6.                         1UL<<12, 1UL<<13, 1UL<<14, 1UL<<15,
   
7.                         1UL<<16, 1UL<<17, 1UL<<18, 1UL<<19,
   
8.                         1UL<<20, 1UL<<21, 1UL<<22, 1UL<<23,
   
9.                         1UL<<24, 1UL<<25, 1UL<<26, 1UL<<27,
   
10.                         1UL<<28, 1UL<<29, 1UL<<30, 1UL<<31 };
    
11. 
    
12. __declspec(naked)
    
13. UINT32 GreaterEqualBit2_57F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
    
14. {
    
15.     __asm
    
16.     {
    
17.         lea     edx, dword ptr[POW2+0x04];
    
18.         mov     eax, dword ptr[esp+0x04];
    
19. 
    
20.         bsr     ecx, eax;
    
21.         mov     ecx, dword ptr[edx+ecx*0x04];
    
22.         push    ecx;
    
23. 
    
24.         xor     eax, ecx;
    
25.         mov     ecx, -1;
    
26.         bsr     ecx, eax;
    
27.         mov     ecx, dword ptr[edx+ecx*0x04];
    
28. 
    
29.         lea     edx, [ecx*0x02];
    
30.         xor     eax, ecx;
    
31.         cmovne  ecx, edx;
    
32. 
    
33.         pop     eax;
    
34.         add     eax, ecx;
    
35. 
    
36.         ret;
    
37.     }
    
38. }

复制代码

15条指令，无移位运算（用查表法）

gxqcn

1. __declspec(naked)
   
2. UINT32 GreaterEqualBit2_58F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
   
3. {
   
4.     __asm
   
5.     {
   
6.         mov     edx, dword ptr[esp+0x04];
   
7.         mov     eax, 1;
   
8. 
   
9.         bsr     ecx, edx;
   
10.         shl     eax, cl;
    
11.         push    eax;
    
12. 
    
13.         xor     edx, eax;
    
14.         bsr     ecx, edx;
    
15.         mov     eax, 0;
    
16.         setne   al;
    
17.         shl     eax, cl;
    
18. 
    
19.         lea     ecx, [eax*0x02];
    
20.         xor     edx, eax;
    
21.         cmovne  eax, ecx;
    
22. 
    
23.         pop     edx;
    
24.         add     eax, edx;
    
25. 
    
26.         ret;
    
27.     }
    
28. }

复制代码

移位（不查表）

gxqcn

1. __declspec(naked)
   
2. UINT32 GreaterEqualBit2_59F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
   
3. {
   
4.     __asm
   
5.     {
   
6.         push    ebx;
   
7.         mov     ebx, dword ptr[esp+0x08];
   
8. 
   
9.         bsr     ecx, ebx
   
10.         mov     eax, 1
    
11.         shl     eax, cl
    
12. 
    
13.         xor     ebx, eax
    
14.         xor     edx, edx
    
15.         bsr     ecx, ebx
    
16.         setne   dl
    
17.         shl     edx, cl
    
18.         add     eax, edx
    
19. 
    
20.         xor     ecx, ecx
    
21.         sub     ebx, edx
    
22.         cmovne  ecx, edx
    
23. 
    
24.         add     eax, ecx
    
25. 
    
26.         pop     ebx;
    
27. 
    
28.         ret;
    
29.     }
    
30. }

复制代码

（改编自无心人的 36#）

gxqcn

在 Intel P4 2.93GHz CPU 上，对 n 从 1 到 2147483648 进行测试，运行时间如下：
24#: 25 s
36#: 35 s
57#: 25 s
58#: 32 s
59#: 27 s

在 AMD Athlon 64 3200+ 上测试则为：
24#: 40 s
36#: 37 s
57#: 37 s
58#: 36 s
59#: 38 s

注：24# 为 liangbch 所写；36# 为 无心人 所写；后3个则为 GxQ 所写。