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

无心人

如果怕兼容性问题，用mm0也可以的 不会有不支持mmx的U了吧

无心人

刚去查MMX的书（中文实体书） movd是有的 也可以考虑下MMX的部分指令 所以59#应该还能优化 不知道GxQ能否给出代码的完整程序 另外，如果程序不用浮点，用不到emms 甚至，只要在浮点前用可以了

gxqcn

1. #include < stdio.h >
2. #include < time.h >
4. typedef unsigned int UINT32;
6. typedef UINT32 func_t( UINT32 );
8. #define FN(ID) GreaterEqualBit2_##ID##F /* ex.: GreaterEqualBit2_24F */
9. #define TEST_VAL 314159265UL
11. /*
13. UINT32 GreaterEqualBit2_24F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
14. {
15. ...
16. }
18. ...
19. */
21. void testFun( void )
22. {
23. time_t t;
24. UINT32 i, j;
25. UINT32 fID[] = { 24, 36, 57, 58, 59 };
26. func_t * funcTable[] = { FN(24), FN(36), FN(57), FN(58), FN(59) };
27. func_t * pfn;
29. // check result
30. for ( i=0; i<sizeof(fID)/sizeof(fID[0]); ++i )
31. {
32. printf( "GreaterEqualBit2_%uF(%u)=0x%X\n",
33. fID[i], TEST_VAL, (funcTable[i])(TEST_VAL) );
34. }
36. // test speed
37. printf( "\n\nn: 1-2^31\n\n" );
38. for ( i=0; i<sizeof(fID)/sizeof(fID[0]); ++i )
39. {
40. pfn = funcTable[i];
42. t = time(NULL);
43. for ( j=0x80000000UL; 0!=j; --j )
44. {
45. pfn( j );
46. }
47. t = time(NULL)-t;
49. printf( "%u#: %u s\n", fID[i], t );
50. }
52. }
54. int main(int argc, char* argv[])
55. {
56. testFun();
58. return 0;
59. }

复制代码

liangbch

我也曾想到查表法，这样，就可以省掉移位指令。这样指令是少了，但增加了访问L1/L2 cache的开销。 我曾试图在不使用查表法的基础上，精简指令条数，但没有取得突破。 在 Intel 和 AMD cpu上的测试结果表明，AMD 对cache 读写不敏感, 而Intel的cpu则对读写cache比较敏感。 在PIV cpu 运行gxq的那个版本，减少的指令条数的正效应 和 cache读写的负效 正好抵消，故和我的版本速度相当。而在AMD cpu运行 这几个版本，gxq 和 无心人的版本因指令较少而胜出。 另外，我认为，测试代码和真实环境应该很难做到一致。测试代码多次读写同一处地址空间。故对RAM的存取实际上是对L1 cache的存取。而在真实环境则存在cache命中失败的情况。故在真实环境下，使用查表法的的实际运行速度应该慢于测试代码。

无心人

__declspec(naked) UINT32 GreaterEqualBit2_75F( UINT32 n /* 1 <= n <= 2^31+2^30 */ ) { __asm { movd mm0, ebx mov ebx, [esp+4] bsr ecx, ebx mov eax, 1 shl eax, cl xor ebx, eax xor edx, edx bsr ecx, ebx setne dl shl edx, cl add eax, edx xor ecx, ecx sub ebx, edx cmovne ecx, edx add eax, ecx movd ebx, mm0 ret; } }

无心人

增加一个测试例子

无心人

Core 2 XEON 1.6G ...\GreaterEqualBit2\Debug>GreaterEqualBit2.exe GreaterEqualBit2_24F(314159265)=0x14000000 GreaterEqualBit2_25F(314159265)=0x14000000 GreaterEqualBit2_36F(314159265)=0x14000000 GreaterEqualBit2_57F(314159265)=0x14000000 GreaterEqualBit2_58F(314159265)=0x14000000 GreaterEqualBit2_59F(314159265)=0x14000000 GreaterEqualBit2_75F(314159265)=0x14000000 24# 24321.769 ms 25# 23220.229 ms 36# 26370.029 ms 57# 22912.707 ms 58# 25381.062 ms 59# 24208.571 ms 75# 23457.994 ms ...\GreaterEqualBit2\Debug>GreaterEqualBit2.exe GreaterEqualBit2_24F(314159265)=0x14000000 GreaterEqualBit2_25F(314159265)=0x14000000 GreaterEqualBit2_36F(314159265)=0x14000000 GreaterEqualBit2_57F(314159265)=0x14000000 GreaterEqualBit2_58F(314159265)=0x14000000 GreaterEqualBit2_59F(314159265)=0x14000000 GreaterEqualBit2_75F(314159265)=0x14000000 24# 24329.577 ms 25# 23221.619 ms 36# 26376.303 ms 57# 22911.231 ms 58# 25355.553 ms 59# 24209.400 ms 75# 23447.267 ms

无心人

可以认为， 查表法没有多少优势

无心人

程序代码和编译后程序 仅要求支持MMX即可 代码 GreaterEqualBit2.cpp (5.48 KB, 下载次数: 0)

2009-2-4 17:15 上传

点击文件名下载附件

程序 GreaterEqualBit2.zip (9.26 KB, 下载次数: 1)

2009-2-4 17:15 上传

点击文件名下载附件

无心人

P4 Xeon 2.0G结果 GreaterEqualBit2_24F(314159265)=0x14000000 GreaterEqualBit2_25F(314159265)=0x14000000 GreaterEqualBit2_36F(314159265)=0x14000000 GreaterEqualBit2_57F(314159265)=0x14000000 GreaterEqualBit2_58F(314159265)=0x14000000 GreaterEqualBit2_59F(314159265)=0x14000000 GreaterEqualBit2_75F(314159265)=0x14000000 24# 43275.580 ms 25# 38754.110 ms 36# 68405.044 ms 57# 41526.848 ms 58# 44159.591 ms 59# 43885.799 ms 75# 43158.709 ms GreaterEqualBit2_24F(314159265)=0x14000000 GreaterEqualBit2_25F(314159265)=0x14000000 GreaterEqualBit2_36F(314159265)=0x14000000 GreaterEqualBit2_57F(314159265)=0x14000000 GreaterEqualBit2_58F(314159265)=0x14000000 GreaterEqualBit2_59F(314159265)=0x14000000 GreaterEqualBit2_75F(314159265)=0x14000000 24# 43023.756 ms 25# 38908.013 ms 36# 68550.773 ms 57# 41309.780 ms 58# 43682.767 ms 59# 43913.680 ms 75# 43546.108 ms ======================================= 25#优势明显