无心人 发表于 2008-4-12 14:10:43

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

#define TestCount 100000000

__declspec (naked)
DWORD __fastcall bitInv(DWORD b, DWORD n)
{
__asm
{       
bswap ecx
mov eax, ecx
and ecx, 0x55555555
and eax, 0xAAAAAAAA
shl ecx, 1
shr eax, 1
or ecx, eax
mov eax, ecx
and ecx, 0x33333333
and eax, 0xCCCCCCCC
shl ecx, 2
shr eax, 2
or ecx, eax
mov eax, ecx
and ecx, 0x0F0F0F0F
and eax, 0xF0F0F0F0
shl ecx, 4
shr eax, 4
or eax, ecx
mov ecx, 32
sub ecx, edx
shr eax, cl
ret
}
}

int main(void)
{
        UINT64 s_u64Frequency = 1;
    UINT64 s_u64Start, s_u64End;
        unsigned long i, TestSize;

        SetThreadPriority(GetCurrentThread(),   THREAD_PRIORITY_TIME_CRITICAL);

        QueryPerformanceFrequency((LARGE_INTEGER *)&s_u64Frequency );
        QueryPerformanceCounter((LARGE_INTEGER *)&s_u64Start );
        for (i = 0; i < TestCount; i ++)
                bitInv(0x12345678, 31);
        QueryPerformanceCounter((LARGE_INTEGER *)&s_u64End );

        printf( "bitInv Elapsed time: %.3f ms\n",
                (double)(( s_u64End - s_u64Start ) * 1000.0 / (double)s_u64Frequency ));


        return 0;
}

//调试好了
//1050ms/1亿次
//全使用逻辑指令为1750ms
//证明BSWAP有很好效果
合21时钟/次
感觉有极大的优化余地

无心人 发表于 2008-4-12 14:35:25

悲哀的发现11楼代码非并行度大，按依赖度，执行组数达15之多
加函数调用开销，优化余地为零！

除非另外的编码思路
======================
查表法失效，并未发现比直接计算快
可能卡在内存读取上

无心人 发表于 2008-4-12 21:50:06

哎
这个问题基本上就到这个地步了
难道要用64k表？

liangbch 发表于 2008-4-13 13:38:32

   若函数 bitInv(DWORD b, DWORD n) 返回 n为二进制数的b的倒序值，则求bitInv(b+1,n)可在 bitInv(DWORD b, DWORD n) 的基础上快速求出。实际应用中，很少单独求bitInv(b,n),而是求 b (b>0, b<2^n)所有的倒序。至于使用递推算法求所有b的算法，我现在手中没有资料，容后补上。
另外，该部分代码所占的时间相比整个FFT或者NTT所占的时间,.比例并不大.故窃以为这部分代码无需使用汇编优化。

无心人 发表于 2008-4-13 14:07:36

呵呵
不汇编化的时间是汇编后的5倍啊
页: 1 [2]
查看完整版本: 二进制倒序数算法