二进制倒序数算法

无心人

#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时钟/次
感觉有极大的优化余地

无心人

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

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

无心人

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

liangbch

   若函数 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所占的时间,.比例并不大.故窃以为这部分代码无需使用汇编优化。

无心人

呵呵
不汇编化的时间是汇编后的5倍啊