倒位序算法（C#实现）

在编写FFT算法的时候，会用到倒位序，倒位序的计算方法：将原序数表示成二进制，然后将二进制首尾反转，得到新的序数序列，即需要的倒位序。

以下称正常排序为正序，倒位序为倒序，十进制数字后面加d标识，二进制数字加b标识。

首先我们剖析一下倒位序的生成规则：

以\(2^3\)序列为例：

正序是相对于上一个序数加1d，对应于二进制加上001b，那么对应于倒序就是二进制加上100b，而且是向右边进位。以下是长度为8的倒位序生成过程：

可以总结出长度为\(2^3\)的倒位序序列，从第\(i\)个倒位序数字\(d_i(十进制)\)生成第\(i+1\)个倒位序数字的规则如下：

• 情况1：第\(i\)个序数倒位加1没有进位，形如\(0**b\)这样的(二进制0打头)，相当于十进制加了\(100b=4d\)，故第\(i+1\)个倒位序数字为\(d_{i+1}=d_i + 4\)；
• 情况2：第\(i\)个序数倒位加1有进位，形如\(1**b\)这样的(二进制1打头)，可以通过减去\(100b=4d\)来实现最高位变成0，但是有进位，所以又要加上\(010b=2d\)，这时要判断二进制第二位是否有进位，判断方法是比较原数字减去了\(4d\)后是否大于等于\(2d\)，如果大于等于\(2d\)，则它必然形如\(01*b\)，加上\(010b\)后有进位，所以先减去\(010b\)，然后再判断加上\(001d\)会不会进位；如果小于小于\(2d\)，则它一定形如\(00*b\)，所以直接加上010b=2d，输出结果。

下面是利用C#输出长度为\(2^n\)的倒位序序列的函数：

//输出长度为2^n的倒位序序列
public int[] reverse(int n)
{
    int len = Convert.ToInt32(Math.Pow(2, n));
    int k ;
    int[] rank = new int[len];
    rank[0] = 0;
    for (int i = 1; i < len; i++)
    {
        k = len / 2;
        if (rank[i - 1] < k)
        {
        	rank[i] = rank[i - 1] + k;
        }
        else
        {
            rank[i] = rank[i - 1];
            while (rank[i] >= k)
            {
                rank[i] = rank[i] - k;
                k = k / 2;
        	}
        	rank[i] = rank[i] + k ;
        }
    }
    return rank;
}