二进制倒序数算法

无心人

一个二进制数字k，小于等于32位，假设为n位
现求它的二进制倒序后的数字

比如k=1011011001 n = 10
输出1001101101

使用最快速算法，汇编C语言都可，
计算n = 31随机数字倒序数1000万次的时间
时间最少的胜利

kenmark

貌似输出比逆序需要是时间更多，最后比拼的不是逆序算法而是输出优化。。

无心人

用在快速卷积计算
如果你那样说
他们就不好做了

gxqcn

这个过程在FFT变换时有用的。

在Debug阶段，可以将出入参用二进制字串输出；
Release阶段，则出入参仍可用DWORD型；
测试阶段，可用一定量的随机数反复调用若干遍，比较各自总耗时即可。

无心人

汇编
BSWAP指令可利用
再加查表

gxqcn

这段，我的处理是没用任何汇编，而是直接写的C代码，
毕竟一旦完成后它就可以作为一个映射表，以后的FFT/FNT等过程直接用就可以了。

无心人

刚写了点
此题目有点困难
单凭一个BSWAP似乎不很好处理

无心人

8位的一个表？

无心人

x := (x and \$55555555) shl  1 or (x and \$AAAAAAAA) shr  1;
   x := (x and \$33333333) shl  2 or (x and \$CCCCCCCC) shr  2;
   x := (x and \$0F0F0F0F) shl  4 or (x and \$F0F0F0F0) shr  4;
   x := (x and \$00FF00FF) shl  8 or (x and \$FF00FF00) shr  8;
   x := (x and \$0000FFFF) shl 16 or (x and \$FFFF0000) shr 16;

  假设ecx = k, edx = n
  mov eax, ecx
  and ecx, 0x55555555
  and eax, 0xAAAAAAAA
  shl ecx, 1
  shr eax, 1
  or ecx, eax
  mov ecx, eax
  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 ecx, eax
  mov eax, ecx
  and ecx, 0x00FF00FF
  and eax, 0xFF00FF00
  shl ecx, 8
  shr eax, 8
  or ecx, eax
  mov eax, ecx
  and ecx, 0x0000FFFF
  and eax, 0xFFFF0000
  shl ecx, 16
  shr eax, 16
  or eax, ecx
  mov ecx, 32
  sub ecx, edx
  shr eax, ecx

无心人

简化下
  bswap ecx
  mov eax, ecx
  and ecx, 0x55555555
  and eax, 0xAAAAAAAA
  shl ecx, 1
  shr eax, 1
  or ecx, eax
  mov ecx, eax
  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, ecx