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

无心人

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

无心人

刚去查MMX的书（中文实体书）
movd是有的
也可以考虑下MMX的部分指令
所以59#应该还能优化
不知道GxQ能否给出代码的完整程序

另外，如果程序不用浮点，用不到emms
甚至，只要在浮点前用可以了

gxqcn

1. #include < stdio.h >
   
2. #include < time.h >
   
3. 
   
4. typedef unsigned int UINT32;
   
5. 
   
6. typedef UINT32 func_t( UINT32 );
   
7. 
   
8. #define FN(ID)      GreaterEqualBit2_##ID##F /* ex.: GreaterEqualBit2_24F */
   
9. #define TEST_VAL    314159265UL
   
10. 
    
11. /*
    
12. 
    
13. UINT32 GreaterEqualBit2_24F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
    
14. {
    
15.     ...
    
16. }
    
17. 
    
18. ...
    
19. */
    
20. 
    
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;
    
28. 
    
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.     }
    
35. 
    
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];
    
41. 
    
42.         t = time(NULL);
    
43.         for ( j=0x80000000UL; 0!=j; --j )
    
44.         {
    
45.             pfn( j );
    
46.         }
    
47.         t = time(NULL)-t;
    
48. 
    
49.         printf( "%u#: %u s\n", fID[i], t );
    
50.     }
    
51. 
    
52. }
    
53. 
    
54. int main(int argc, char* argv[])
    
55. {
    
56.     testFun();
    
57. 
    
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#优势明显