hanyeah

在实现FFT(快速Fourier变换)计算的时候，第一步要做的就是实现码位(二进制码)倒序。

有一种算法，叫做雷德（Rader）算法。

关于雷德算法，可以看这个：

FFT中的Rader算法：码率倒序

用js写了一遍，如下：

// 雷德（Rader）算法
function rader(src, N){
	var next = 0;
	var k = N>>1;
	while(k){
		if(k>src){
			next = src + k;
			break;
		}
		else{
			src -= k;
			k = k >> 1;
		}
	}
	return next;
}

// 位运算 实现加法
// http://blog.csdn.net/zhongjiekangping/article/details/6855864
function sum0(a,b){
	return (a^b) +((a&b)<<1);
}
// 自己写的，同雷德（Rader）算法，只是b是N>>1。
function sum(a,b){
	var c = a^b;
	var d = a&b;
	while(d){
		d=d>>1;
		if(d^(d&c)){
			break;
		}
		else{
			c=d^c;
		}
	}
	return c+d;
}

// 下边是测试代码
var arr = [];
var src = 0;
var n = 3;
var N = 1<<n; 
for(var i=0;i<=N;i++){
	arr[i] = src;
	src = rader(src,N);
}
console.log(arr);

src = 0;
var arr2 = [];
var N2 = N>>1;
for(var i=0;i<=N;i++){
	arr2[i] = src;
	src = sum(src,N2);
}
console.log(arr2);

n = 10;
N = 1<<n;
N2 = N>>1;
src = 0;
console.time("rader:");
for(var i=0;i<N;i++){
	src = rader(src,N);
}
console.timeEnd("rader:");

src = 0;
console.time("hanyeah:");
for(var i=0;i<N;i++){
	src = sum(src,N2);
}
console.timeEnd("hanyeah:");

还是雷德（Rader）算法快。

生成倒序数耗时很短，在做fft的时候可以忽略。