一个快速得到bit位索引的算法

无心人

附详细代码
并请终止任何当前占CPU程序

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

DWORD bits[32];

void find(DWORD a, DWORD * b, DWORD *c)
{
        __asm
        {
      mov   eax, dword ptr [a]      
      xor   esi, esi   
    loop1:      
      bsr   edi, eax
      je exit1
      xor   eax, dword ptr [bits + 4 * edi]
      mov   dword  ptr [b + 4*esi], edi            
      inc   esi   
      jmp   loop1
    exit1:      
      mov   dword ptr [c], esi
        }
}

DWORD find_by_GxQ(DWORD code, DWORD index[33])
{
    __asm
    {
        mov     ecx, code;

        xor     eax, eax;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 0;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 1;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 2;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 3;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 4;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 5;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 6;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 7;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 8;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 9;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 10;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 11;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 12;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 13;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 14;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 15;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 16;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 17;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 18;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 19;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 20;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 21;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 22;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 23;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 24;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 25;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 26;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 27;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 28;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 29;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 30;
        adc     eax, 0;

        shr     ecx, 1;
        mov     dword ptr[index + 4*eax], 31;
        adc     eax, 0;

        // 休止符
        mov     dword ptr[index + 4*eax], -1;
    }
}

int   main(int   argc,   char *   argv[])
{
::SetThreadPriority(::GetCurrentThread(),   THREAD_PRIORITY_TIME_CRITICAL);
LARGE_INTEGER   lTimestart,   lTimeEnd,   liFreq;

DWORD c, bitMask = 1, index[33];

for (DWORD i = 0; i < 31; i ++)
{
  bits[i] = bitMask;
  bitMask <<= 1;
}

QueryPerformanceCounter(&lTimestart);
for(DWORD   i   =   0;   i   <   1000000;   i++){
  find(i,  &index[0], &c);//   调用bit扫描函数
}
QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);

double   dbMs   =   ((double)   (lTimeEnd.QuadPart   -   lTimestart.QuadPart)   *   1000)   /   (double)liFreq.QuadPart;
printf("yaos: %.3f\n", dbMs);

QueryPerformanceCounter(&lTimestart);
for(DWORD   i   =   0;   i   <   1000000;   i++){
  find_by_GxQ(i,  index);//   调用bit扫描函数
}
QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);

dbMs   =   ((double)   (lTimeEnd.QuadPart   -   lTimestart.QuadPart)   *   1000)   /   (double)liFreq.QuadPart;
printf("GXQ: %.3f\n", dbMs);

system("Pause");

return   0;
}

无心人

测试机器P4 XEON 2.0 X 2, 1G DDR
多次比较时间

E:\yaojialin\FindBits\Debug>findbits
yaos: 154.030
GXQ: 174.165
请按任意键继续. . .

E:\yaojialin\FindBits\Debug>findbits
yaos: 153.931
GXQ: 174.422
请按任意键继续. . .

E:\yaojialin\FindBits\Debug>findbits
yaos: 153.751
GXQ: 171.132
请按任意键继续. . .

E:\yaojialin\FindBits\Debug>findbits
yaos: 154.908
GXQ: 171.753
请按任意键继续. . .

E:\yaojialin\FindBits\Debug>findbits
yaos: 156.030
GXQ: 171.409
请按任意键继续. . .

E:\yaojialin\FindBits\Debug>findbits
yaos: 154.036
GXQ: 171.994
请按任意键继续. . .

E:\yaojialin\FindBits\Debug>findbits
yaos: 154.855
GXQ: 173.272
请按任意键继续. . .

gxqcn

原帖由 无心人 于 2008-3-10 10:07 发表
...
for(DWORD   i   =   0;   i   <   1000000;   i++){
  find(i,  &index[0], &c);//   调用bit扫描函数
}
...

这个测试是不科学的，因为被测数(i)的高12位永远为0，若用判断语句可提前退出，
所以对被测函数不公平。比较好的是用随机数（我原来测试是$2^24=16777216$个随机数）

另外，你的函数在我的机器上无法运行。看了一下你的汇编，错误比较多：
void find(DWORD a, DWORD * b, DWORD *c)
{
        __asm
        {
      mov   eax, dword ptr [a]      
      xor   esi, esi   
    loop1:      
      bsr   edi, eax
      je exit1
      xor   eax, dword ptr [bits + 4 * edi]
      mov   dword  ptr [b + 4*esi], edi            
      inc   esi   
      jmp   loop1
    exit1:      
      mov   dword ptr [c], esi
        }
}
其中：bsr按你的思路应为bsf，
另外，请自己debug一下，b,c是否写成功？（需要将它们地址存到寄存器中才可访问内容）

gxqcn

原帖由 无心人 于 2008-3-10 10:06 发表
总感觉不对劲

终于觉醒了
似乎我是测试的1000万, 你们测试的是100万
把GXQ代码和我代码聚集在一起

终于比较出来了
还是我的快

我冤啊

你看错了，我们测试的是 0x1000000 = 16777216 个随机数，比你的更大更好。
在公司里我无法下载论坛附件，但从你给出的代码感觉非常不合理。

无心人

那你测试下

我是根据100万做的

无心人

咱测全32位数字如何???
0 - FFFFFFFF

我就想看看位操作和技巧到底谁好
===========================
另外你说的不对
位扫描不管数字如何
总执行周期就是32
0也要一位位扫描下去
不过是CPU代替循环而已

gxqcn

你的汇编犯有低级错误，我已在 23# 中给你指出来了。

无心人

能通过编译啊

老大

gxqcn

编译过，但运行结果错，那就毫无意义了。

算了，好事做到底，把你的代码修正过来了，请你自测吧（在我这儿你的远远落后）：

1. DWORD bits[32];
   
2. void find(DWORD a, DWORD * b, DWORD *c)
   
3. {
   
4.     __asm
   
5.     {
   
6.         mov   eax, a;
   
7.         mov   edx, dword ptr b;
   
8.         xor   esi, esi;
   
9. loop1:
   
10.         bsf   edi, eax;
    
11.         je exit1;
    
12.         xor   eax, dword ptr [bits + 4 * edi];
    
13.         mov   dword  ptr [edx + 4*esi], edi;
    
14.         inc   esi;
    
15.         jmp   loop1;
    
16. exit1:
    
17.         mov   edx, dword ptr c;
    
18.         mov   dword ptr [edx], esi;
    
19.     }
    
20. }

复制代码

调整一下寄存器名，代码如下：

1. DWORD bits[32];
   
2. void find(DWORD a, DWORD * b, DWORD *c)
   
3. {
   
4.     __asm
   
5.     {
   
6.         mov   edx, a;
   
7.         mov   edi, dword ptr b;
   
8.         xor   eax, eax;
   
9. loop1:
   
10.         bsf   ecx, edx;
    
11.         je    exit1;
    
12.         xor   edx, dword ptr [bits + 4 * ecx];
    
13.         mov   dword  ptr [edi + 4*eax], ecx;
    
14.         add   eax, 1;
    
15.         jmp   loop1;
    
16. exit1:
    
17.         mov   edi, dword ptr c;
    
18.         mov   dword ptr [edi], eax;
    
19.     }
    
20. }

复制代码

无心人

老大啊
bsr乃反向位扫描啊

我发这的意思
基于下面的疑惑

你们汇编远大于我的代码的4倍
假使你们以每周期4个指令执行
也不能远大于我的时间

我代码应该没明显的阻塞地方

并不是说谁的代码不好
我弄不明白我不死心
==========================
我这里我的162 你的171 按你改的代码, 比我自己的慢4ms