论坛 › 编程擂台 › 二进制倒序数算法

无心人 发表于 2008-4-11 16:45:20

二进制倒序数算法

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

比如k=1011011001 n = 10
输出1001101101

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

kenmark 发表于 2008-4-11 19:57:54

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

无心人 发表于 2008-4-11 20:38:25

:)

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

gxqcn 发表于 2008-4-11 20:40:43

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

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

无心人 发表于 2008-4-11 20:43:14

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

gxqcn 发表于 2008-4-11 20:50:02

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

无心人 发表于 2008-4-11 21:03:17

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

无心人 发表于 2008-4-11 21:04:19

:)

8位的一个表？

无心人 发表于 2008-4-11 21:30:56

x := (x and \$55555555) shl1 or (x and \$AAAAAAAA) shr1;
   x := (x and \$33333333) shl2 or (x and \$CCCCCCCC) shr2;
   x := (x and \$0F0F0F0F) shl4 or (x and \$F0F0F0F0) shr4;
   x := (x and \$00FF00FF) shl8 or (x and \$FF00FF00) shr8;
   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

无心人 发表于 2008-4-11 21:39:03

简化下
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

查看完整版本: 二进制倒序数算法