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

gxqcn

你的测试结论也是可能的。
我查了一下 ADC r,i 指令周期表，AMD的远优于Intel的，不得不赞一下。

你将 bsr 指令的含义理解反了，这让人不得不怀疑你是否真正debug过你的代码？

无心人

呵呵
那也不说明我错误啊
======================
我明白我错在哪里了

每个循环的bsr都要从头开始查找
所以实际上成了个o(N^2)算法
所以需要修改代码记住当前位置
但可能得不偿失

无心人

它ADC是优秀了
反过来bsr却不行了

======================
  bsr指令称为逆向扫描指令，指令格式为BSR   OPRD1,   OPRD2。功能是从左向右扫描字或双字操作数OPRD2中第一个含"1"的位，并把扫描到的第一个含“1”的位的位号送操作数OPRD1。
========================
我没理解错误, 从高到低就是反向
我有386的详细指令的中文纸质书
还是有90%把握的啊

无心人

无论如何之前在两个论坛的该问题代码全部声明作废
以下述代码为准

DWORD find_by_yaos(DWORD code, int index[33])
{
    __asm
    {
        mov     ecx, code;
        mov     edx, dword ptr index;
        xor     eax, eax
loop1:
       bsr     ebx, ecx
       je exit1
      btr      ecx, ebx
     mov    dword ptr[edx + 4*eax],  ebx
     inc eax
      jmp loop1
  exit1:
    mov     dword ptr[edx + 4*eax], -1;
      }
}

//另外还一个版本是对GxQ代码的改动的
//但不知是否可行
//把他代码中shr改bt

gxqcn

• adc 是常用指令；bsr 不常用，也不推荐使用！(to: 33#)
  
• 用 BSF(Bit Scan Forward)，还是 BSR(Bit Scan Reverse)？(to: 33#)
  仅取决于提供给客户的 index[] 有效元素的排列顺序，前者为升序，后者为降序！
  
• 友情提醒：bsf 指令可能比 bsr 指令更快！(to: 33#)
  
• 友情提醒：inc/dec 指令一般没有 add/sub 指令快！(to: 29#)
  
• 友情提醒：btr 指令（以及 bt 指令）甚至没有 shr 指令快！(to: 34#)

无心人

2、再考虑下， 是一样
3、针对寄存器的，intel是一致的
4、我受的教育怎么是inc快于add
对eax时间是相同的
5、btr在这里没读内存的需求

无心人

到这个地步了
无论你还是我都无法大幅度改进了

咱算下函数执行指令周期数吧

我总觉得周期太长

无心人

大数据量测试
你的比我代码快了

全0-2^32测试(但没停止别的程序)
yaos: 933.145
GXQ: 833.881

无心人

833.881/2 = 417周期

有点太长
除去循环和call指令消耗

也至少350

无心人

/*
yaos: 3.146
      CPU Clock Used: 1064
GXQ: 2.896
      CPU Clock Used: 700
*/
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

__int64 GetCPUCounter(void)
{
        __asm rdtsc;
}
void find_by_yaos(DWORD a, DWORD index[33])
{
   __asm
    {
        mov   edx, a;
        mov   edi, dword ptr index;
        xor   eax, eax;
loop1:
        bsr   ecx, edx;
        je    exit1;
        btr   edx, ecx;
        mov   dword  ptr [edi + 4*eax], ecx;
        inc eax;
        jmp   loop1;
exit1:
        mov   dword ptr [edi + 4*eax], -1;
    }
}

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;
__int64 CounterStart, CounterStop;

DWORD index[33];

QueryPerformanceCounter(&lTimestart);
for(DWORD   i   =   0;   i   <=   0x1000000;   i++){
  find_by_yaos(i,  index);//   调用bit扫描函数
}

CounterStart = GetCPUCounter();
find_by_yaos(0xFFFFFFFF, index);
CounterStop = GetCPUCounter();

QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);

double   dbMs   =   ((double)   (lTimeEnd.QuadPart   -   lTimestart.QuadPart))   /   (double)liFreq.QuadPart;
printf("yaos: %.3f\n", dbMs);
printf("      CPU Clock Used: %ld\n", CounterStop - CounterStart);

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

dbMs   =   ((double)   (lTimeEnd.QuadPart   -   lTimestart.QuadPart))   /   (double)liFreq.QuadPart;
printf("GXQ: %.3f\n", dbMs);
printf("      CPU Clock Used: %ld\n", CounterStop - CounterStart);

//system("Pause");

return   0;
}