一种没什么人用但是香到爆的位反转解决方法, 可能与设备兼容性有关.

基于大小端转换的位反转.

数字信号处理学到FFT, 学完自己写点东西玩玩.
处理初始的两点DFT时出错, 检查代码原因是输入排序并不是按照我想的对称排序.
书上给了一种方法是按位反转可以得到对应序列.

在Google上搜了一下reversing bits大部分结果都是遍历或者使用分而治之的方法.
带着凡是位操作都有可能有更精妙的方法思考了一下, 正好昨天看CortexM3的时候想起来CPU可能有大小端转换的指令, 稍微查了一下发现处理器真有一个指令可以用上.
IA64的bswap, ARM CM3的REV, MSP430的SWPB, TMS320的FLIP. 这四个指令可以对BE和LE进行相互转换. 当然ARM有直接位反转的指令没这个必要多好几步.
这几个指令直接把any bits reverse转换成了8bits reverse., 可以节省时间了.

用内联ASM写了一点东西发现可以用, 但是输入和输出没有办法指定为寄存器, 再稍微查了一下Google发现对应GCC里面有一个好玩的内置函数__builtin_bswap<bits>, 使用这个函数的话可以根据平台自动选择合适的指令.
在确定方向之后去Google找fastest 8bit reversing然后在StackOverflow找到了满意的回答.
结合两者得到了满意的结果. 稍微优化一下把变量放寄存器里面.

1
2
3
4
5
6
7
8
9
10
11
12

#pragma once
inline uint64_t reverseBits(uint32_t n) {
    register uint64_t tmp = n;
    tmp = __builtin_bswap64(tmp2);
    // 0x1004017c9  
    tmp = (tmp & 0xF0F0F0F0F0F0F0F0) >> 4 | (tmp & 0x0F0F0F0F0F0F0F0F) << 4;
    tmp = (tmp & 0xCCCCCCCCCCCCCCCC) >> 2 | (tmp & 0x3333333333333333) << 2;
    tmp = (tmp & 0xAAAAAAAAAAAAAAAA) >> 1 | (tmp & 0x5555555555555555) << 1;
    // 0x100401850  
    // length = 135 ops = 28
    return tmp;
}

增加任意位数反转支持

再回去看看书, FFT需要的位反转映射是有位数限定的.
那只要找出最高位的位置再把结果右移就可以解决了. 或者使用循环左移也是可以的. 最开始的想法仍然是使用log2函数快速解决, 但是log2输出是双浮点. 凭着跟2^n有关的应该有在位操作上的简便解法思考了一下
在看__builtin_bswap64的时候记得有一个函数是可以计算前导0和后导0的, 查了一下了解到是__builtin_clz, 再去查了一下Instructions Set发现ARM和IA64都有指令计算前导0和后导0.
闲得无聊浏览Linux的kernel.h记得有几个很奇怪的宏, 其中一个就是round_*函数, 明明是整数却还要round, 最开始以为是给定点小数用的, 现在看起来确实自有用处.
联合使用round_up和__builtin_clz相当于(int)(ceil(log2(N))).
剩下的拼凑函数就好解决了. 最后再从Google抄一个100%正确的位反转算法写一个测试和自己程序的输出用assert进行比较, 并没有报错, 说明这个方法也是100%正确的.
用objdump反汇编以后定位到核心位置在64bit处理这块用了28个指令, 使用了135bytes. 和自己最开始写8位转换的36指令129bytes确实快不少.

1
2
3
4
5
6

#pragma once
#define __round_mask(x, y) ((__typeof__(x))((y)-1))
#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
inline uint64_t bitreverse_ranged(uint64_t input, uint64_t max_N){
    return reverseBits(input) >> __builtin_clzll(round_up(max_N, 2) - 1);
}

最后吹爆FFT. 在复杂度上完爆DFT.

闲得无聊去leetcode试了一下32位简化版.