基于4的FFT变换

#include 
#include 
#include “math.h“
using namespace std;

const double pi = 3.1415926535897932;
const int N=256;

class complex
{
public:
	//无参构造函数
	complex（）
	{
		re=0;
		im=0;
	}
	//有参构造函数
	complex（double realdouble imag）
	{
		re=real;
		im=imag;
	}
	//加法
	complex operator + （complex& c）
	{
		return complex（ re + c.re  im + c.im ）;
	}
	//减法
	complex operator - （complex& c）
	{
		return complex（ re - c.re  im - c.im ）;
	}
	//乘法
	complex operator * （complex& c）
	{
		return complex（ （re * c.re）-（im * c.im）  （re * c.im）+（im * c.re） ）;
	}
	//除法
	complex operator / （complex& c）
	{
		return complex（ （ re*c.re + im*c.im ）/（ c.re*c.re + c.im*c.im ）
			（（im * c.re）-（re * c.im））/（（c.re*c.re）+（c.im*c.im）） ）;
	}
	//除2
	void half（）
	{
		re=re/2;
		im=im/2;
	}

	//输出到ostream
	void insert（ostream& out）
	{
		if（re>=0） cout<<“ “;
		out<=0）?‘+‘:‘-‘） <<‘j‘<< （（im>=0）?im:（0-im））;
	}
	//显示
	void show（）
	{
		cout<=0）?‘+‘:‘-‘） <<‘j‘<< （（im>=0）?im:（0-im）） ;
	}
	//设值
	void setValue（double realdouble imag）
	{
		if（real>0.00000001||real< -0.00000001） re=real;
		else re=0;
		if（imag>0.00000001||imag< -0.00000001） im=imag;
		else im=0;
	}

private:
	double reim;
};

//流输出
ostream& operator << （ostream& out complex c）
{
	c.insert（out）;
	return out;
}


//获得Wn
void getW（complex w[]int len）
{
	for（int i=0;i	{
		w[i].setValue（ cos（0 - pi*2*（i）/len）  sin（0 - pi*2*（i）/len） ）;
	}
}

//倒序重排
void resort（complex X[]）
{
	double len=N;
	int L=log（len）/log（double（4））;
	int in;
	complex *temp = new complex[N];
	for（i=0;i		temp[i]=X[i];
	for（i=0;i	{
		n=i;
		n=（（n&0xcccc）>>2）|（（n&0x3333）<<2）;
		n=（（n&0xf0f0）>>4）|（（n&0x0f0f）<<4）;
		n=（（n&0xff00）>>8）|（（n&0x00ff）<<8）;
		n=n>>（2*（8-L））;
		X[i]=temp[n];
	}
	delete[]temp;
}
//基2时间FFT
void FFT2t（complex x[]）
{
	//初始化
	double len=N;
	int L=log（len）/log（double（4））;
	int lgkm;
	int k0k1k2k3k4;
	int gc2gi1gi2;
	complex *temp = new complex[N];
	complex *w = new complex[N];
	complex *X=new complex[4];
	complex j（01）;
	getW（wN）;
	resort（x）;
	//开始迭代运算
	for（l=1;l<=L;l++）
	{
		gc2=1<<（2*（L-l））;

		gi2=1<<（2*l）;
		gi1=1<<（2*（l-1））;

		for（g=0;g			for（k=0;k			{
				k0=k+g*gi2;
				m=gc2*k;
				k1=k0;k2=k1+gi1;k3=k2+gi1;k4=k3+gi1;
				
				X[0]=x[k1];X[1]=w[m]*x[k2];X[2]=w[2*m]*x[k3];X[3]=w[3*m]*x[k4];

				temp[k1]=X[0]+X[1]+X[2]+X[3];
				temp[k2]=X[0]-j*X[1]-X[2]+j*X[3];
				temp[k3]=X[0]-X[1]+X[2]-X[3];
				temp[k4]=X[0]+j*X[1]-X[2]-j*X[3];
			}
		for（int i=0;i			x[i]=temp[i];
	}
	delete[]Xw;
}

//主函数
void main（）
{
	//初始化
	complex q（0.90.3）;
	complex x[N]w[N];
	int i;
	getW（wN）; //获取Wn序列
	x[0].setValue（21）;
	for（i=1;i	{
		x[i]=x[i-1]*q;
	}
	//输出原序列
	cout<<“原序列：“<	for（i=0;i<16;i+=2）
	{
		cout<