二进制倒序数算法

无心人

#include #include #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倍啊