一个快速得到bit位索引的算法 - 第3页 - 算法交流 - 数学研发论坛

无心人 发表于 2008-3-10 10:07:43

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

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

DWORD bits;

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

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

   xor eax, eax;

   shr ecx, 1;
   mov dword ptr, 0;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 1;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 2;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 3;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 4;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 5;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 6;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 7;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 8;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 9;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 10;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 11;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 12;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 13;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 14;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 15;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 16;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 17;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 18;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 19;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 20;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 21;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 22;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 23;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 24;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 25;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 26;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 27;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 28;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 29;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 30;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 31;
   adc eax, 0;

   // 休止符
   mov dword ptr, -1;
}
}

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

DWORD c, bitMask = 1, index;

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

QueryPerformanceCounter(&lTimestart);
for(DWORD i = 0; i < 1000000; i++){
find(i,&index, &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;
}

无心人 发表于 2008-3-10 10:10:12

测试机器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:38:18

原帖由无心人于 2008-3-10 10:07 发表 http://bbs.emath.ac.cn/images/common/back.gif
...
for(DWORD i = 0; i < 1000000; i++){
find(i,&index, &c);// 调用bit扫描函数
}
...

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

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

gxqcn 发表于 2008-3-10 10:49:15

原帖由无心人于 2008-3-10 10:06 发表 http://bbs.emath.ac.cn/images/common/back.gif
总感觉不对劲

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

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

我冤啊

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

无心人 发表于 2008-3-10 11:22:58

那你测试下

我是根据100万做的

无心人 发表于 2008-3-10 11:36:48

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

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

gxqcn 发表于 2008-3-10 11:39:13

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

无心人 发表于 2008-3-10 11:54:50

:)
能通过编译啊

老大

gxqcn 发表于 2008-3-10 12:54:28

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

算了，好事做到底，把你的代码修正过来了，请你自测吧（在我这儿你的远远落后）：DWORD bits;
void find(DWORD a, DWORD * b, DWORD *c)
{
__asm
{
   mov eax, a;
   mov edx, dword ptr b;
   xor esi, esi;
loop1:
   bsf edi, eax;
   je exit1;
   xor eax, dword ptr ;
   mov dwordptr , edi;
   inc esi;
   jmp loop1;
exit1:
   mov edx, dword ptr c;
   mov dword ptr , esi;
}
}调整一下寄存器名，代码如下：DWORD bits;
void find(DWORD a, DWORD * b, DWORD *c)
{
__asm
{
   mov edx, a;
   mov edi, dword ptr b;
   xor eax, eax;
loop1:
   bsf ecx, edx;
   je exit1;
   xor edx, dword ptr ;
   mov dwordptr , ecx;
   add eax, 1;
   jmp loop1;
exit1:
   mov edi, dword ptr c;
   mov dword ptr , eax;
}
}

无心人 发表于 2008-3-10 13:35:07

老大啊
bsr乃反向位扫描啊

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

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

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

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

页: 1 2 [3] 4 5 6 7

数学研发论坛's Archiver