快速离散傅里叶变中的倒位序号问题

之前写过一篇关于倒位序号的算法，实现简单，但是算法不易理解。再写一个容易理解，但是感觉很low的。。。。

首先解释一下倒位序号。。

倒位序号就是指将数n的二进制码的位序颠倒后的数n^,比如说n=6,6的二进制数为110，倒序就为011，那么n^就等于3；

基本的思路就是，先求n的二进制数，利用的方法就是经典的“初二取余法”,求出来的就是倒序的二进制；

如

快速离散傅里叶变中的倒位序号问题

最后在将二进制转换成对应的十进制即可。。。

给出代码（只实验了8个数的）

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define N 8
int reverse(int scr,int num);
int main()
{
    int scr[N]={0,1,2,3,4,5,6,7};
    printf("原数组为：
");
    for(int i=0;i<N;i++)
    {
        printf("%d  ",scr[i]);
    }
    printf("
");

    int des[N];


    int n=0; //求有几个二进制位，比如8个数对应3个二进制位，16个对应4个二进制位
    int num=N;
    while(  (num/2)  !=0)
    {
        num=num/2;
        n++;
    }
//
    for( i=0;i<N;i++)
    {
        des[i]=reverse(scr[i],n);
    }


    printf("变化后的数组为：
");
    for(i=0;i<N;i++)
    {
        printf("%d  ",des[i]);
    }
    printf("
");

    return 0;
}

//位码倒序的实现函数
//输入参数为原位，输出为其倒序
//返回值为二进制的位数
int reverse(int scr,int n)
{
    
    

    //用于保存将十进制转换成的二进制（是倒序的）
    int binary[10]={0};//2的10次方就是1024如果仅仅是验证算法，这点空间就够了
    //利用商余法求十进制数对应的二进制（倒序）
    int index=0;//用于控制下标移动

    while(   scr  !=0   )
    {
        
        binary[index]=scr%2;//求余数
        scr=scr/2;//求商，作为下次的被除数
        index++;
    }
    
    //然后把binary转换成十进制

    int sum=0;//和

    for(int i=0;i<n;i++)
    {
    
        sum+=binary[i]*pow( 2, (n-i-1) );

    }

    return sum;
}

快速离散傅里叶变中的倒位序号问题

相关推荐