一个快速得到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