一个快速得到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 #include #include __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; }