求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;
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 };
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];
20. bsr ecx, eax;
21. mov ecx, dword ptr[edx+ecx*0x04];
22. push ecx;
24. xor eax, ecx;
25. mov ecx, -1;
26. bsr ecx, eax;
27. mov ecx, dword ptr[edx+ecx*0x04];
29. lea edx, [ecx*0x02];
30. xor eax, ecx;
31. cmovne ecx, edx;
33. pop eax;
34. add eax, ecx;
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;
9. bsr ecx, edx;
10. shl eax, cl;
11. push eax;
13. xor edx, eax;
14. bsr ecx, edx;
15. mov eax, 0;
16. setne al;
17. shl eax, cl;
19. lea ecx, [eax*0x02];
20. xor edx, eax;
21. cmovne eax, ecx;
23. pop edx;
24. add eax, edx;
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];
9. bsr ecx, ebx
10. mov eax, 1
11. shl eax, cl
13. xor ebx, eax
14. xor edx, edx
15. bsr ecx, ebx
16. setne dl
17. shl edx, cl
18. add eax, edx
20. xor ecx, ecx
21. sub ebx, edx
22. cmovne ecx, edx
24. add eax, ecx
26. pop ebx;
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 所写。