雷德算法
一个小算法的感觉。
拿一个0到2^n-1的自然数序列。
比方说
0 1 2 3 4 5 6 7
我们转换为二进制状态，那么这个序列就是
000 001 010 011 100 101 110 111
接下来我们模拟FFT的位置交换，即：
0 1 2 3 4 5 6 7
0 2 4 6 1 3 5 7
0 4 2 6 1 5 3 7
发现最终的序列变为了
000 100 010 110 001 101 011 111
雷德算法就是用于求出这个倒序的数列。
那么开始抄别人的玩意：
由上面的表可以看出，按自然顺序排列的二进制数，其下面一个数总是比其上面一个数大1，即下面一个数是上面一个数在最低位加1并向高位进位而得到的。
而倒位序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位进位而得到。
I、J都是从0开始，若已知某个倒位序J，要求下一个倒位序数：
应先判断J的最高位是否为0。
这可与k=N/2相比较，因为N/2总是等于100的。
如果k>J，则J的最高位为0，只要把该位变为1（J与k=N/2相加即可），就得到下一个倒位序数；
如果K<=J，则J的最高位为1，可将最高位变为0（J与k=N/2相减即可）。然后还需判断次高位，这可与k=N\4相比较，若次高位为0，则需将它变为1（加N\4即可）其他位不变，既得到下一个倒位序数；若次高位是1，则需将它也变为0。然后再判断下一位……
代码如下：
void Rader(int len) {
int vi,vj,vt=0;
for(vi=0; vi<len; vi++) {
if(vi>vt)std::swap(Po[vi],Po[vt]);//否则就交换两次白忙活了
for(vj=(len>>1); (vt^=vj)<vj; vj>>=1);
}
}
Po就是直接储存的数字了。
这里直接搬了FFT的代码……