概述

本文列出了倒位序重排的原始问题，数列的规律和性质，以及暴力解法、kaldi中的迭代解法、倒位序重排三种解法，并给出了理论证明。最后对问题做了部分延伸。

求解问题

先忽略“倒位序重排”这一串名词，看一个问题。用一张图直观描述一个序列长度为16的操作过程。图片来自Radix 2 FFT。

根据图示描述，对于输入序列，按偶数位置的数依次放左边，奇数位置的数依次放右边的方式，不断二分。下文简单描述为奇偶二分。

现在问题来了：有一个2的n次幂的序列，按这样的奇偶二分操作后，如何求最终得到的序列？

因为求解过程只与元素所在的位置相关，为了方便操作，我们将这个序列看成是从0到n-1的一串有序数列。因为一旦求得这个结果序列，即找到了元素应该放置的新位置。

悄悄给你们透点风，我在入门快速傅立叶变换FFT，它需要这个东西。

暴力解法

一切还是从简单的方法入手，先写个基础程序暴力求解，除了帮助理解问题以外，还可以作为验证程序。
先就不动脑子了，让双手操作起来。不就是偶数左边放，奇数右边放吗，如此二分下去，直到不可分。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import sys

def split_even_odd(seq):
    if len(seq) <= 2:
        return seq

    # 以步长为2做切片
    even = seq[::2]
    odd = seq[1::2]

    even = split_even_odd(even)
    odd = split_even_odd(odd)
    return even + odd

if __name__ == '__main__':
    log2N = int(sys.argv[1])
    seq = list(range(1<<log2N))
    print(seq, sep=',')

    new_seq = split_even_odd(seq)
    print(new_seq, sep=',')

查看输出结果：

[leo@leo-m rev]$ python rev.py 1
[0, 1]
[0, 1]
[leo@leo-m rev]$ python rev.py 2
[0, 1, 2, 3]
[0, 2, 1, 3]
[leo@leo-m rev]$ python rev.py 3
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 4, 2, 6, 1, 5, 3, 7]
[leo@leo-m rev]$ python rev.py 4
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

当有 $N$ 个数, 且 $N$ 很大时，在树形结构中可以看出分 $log_2^N$ 层，每一层都会遍历所有数，时间复杂度为 $O(N*logN)$。
而且这个程序太简单，有一些缺点：

• 其中操作数组切片，伴随内存申请和拷贝，影响效率。
• 使用递归，在大 $N$ 的序列下，可能导致栈溢出。

这些从技术上是可以优化的，但是我不想折腾了，因为已经达到验证程序的目的。

kaldi中的迭代解法

代码印象

kaldi是语音识别方面的开源实现工具或者说是框架。kaldi中改进解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

brseed_ = new MatrixIndexT[1 << lg2];
brseed_[0] = 0;
brseed_[1] = 1;
for (j = 2; j <= lg2; j++) {
  imax = 1 << (j - 1);
  for (i = 0; i < imax; i++) {
    brseed_[i] <<= 1;
    brseed_[i + imax] = brseed_[i] + 1;
  }
}

用草稿大概推算一下，第一个for循环log2N步，相当于二分的树形结构的层数。然后每层在上一层的基础上*2加上*2 + 1就可得出。而基础层是[0, 1]两个数，第二层就是[0, 2, 1, 3]，第三层就是[0, 4, 2, 6, 1, 5, 3, 7]，以此类推。
是不是看到了上面暴力解法的结果了？这么神奇的吗？这些数还有这种规律？
这个算法循环log2N次，每次循环中大约再循环(第二个for)2, 4, 8,...,N，算下来时间复杂度为 $O(N)$。并且只有移位和加法，没有频繁的内存申请拷贝等，非常高效。

其它一些神奇的规律

隐藏的序列

除了上面的kaldi层*2和*2 + 1的规律外，还能发现各项数据中都有[0, 2, 1, 3]这段序列的影子。

• 比如长度为8的结果，[0, 4, 2, 6]其实是[0, 2, 1, 3] * 2。而全结果为[[0, 4] + 0, [0, 4] + 2, [0, 4] + 1, [0, 4] + 3]。
• 比如长度为16的结果，[0, 8, 4, 12]其实是[0, 2, 1, 3] * 4。而[0, 8, 4, 12, 2, 10, 6, 14]又是[[0, 8] + 0, [0, 8] + 2*2, [0, 8] + 2*1, [0, 8] + 2*3]。其它数据也有类似结果。

固定的位置规律

# 长度4
[0, 1, 2, 3]
[0, 2, 1, 3]

# 长度8
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 4, 2, 6, 1, 5, 3, 7]

# 长度16
[0, 1, 2, 3,  4,  5, 6,  7, 8, 9, 10, 11, 12, 13, 14, 15]
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9,  5, 13,  3, 11,  7, 15]

通过上面的序列可以发现:

• 首尾两个数变换前后没有任何移动。看长度为4时的0和3，长度为8时的0和7，等等。
• 第二个位置上的数，会移到中位数后面，比如长度为16时的1。
• 倒数第二个位置上的数，会移到中位数前面，比如长度为16时的14。
• 中位数后面的那个数，会移到第二个位置，比如长度为16时的8。
• 中位数前面的那个数，会移到倒数第二个位置，比如长度为16时的7。
• 中位数前或者后的第二个数，位置不变，比如长度为16时的6，9。

等等等等规律，让这个序列看起来很神奇。

用数学解释kaldi的迭代方法

暴力解法中，我们的视角是从序列的操作出发。而从数据上看，是能发现很多规律的。而kaldi中的方法就是从数据的数学关系角度出发的。
kaldi的 代码 使用的是一种迭代办法，某一层的结果是对上一层结果的变换。所以要证明的是迭代关系。

首先我们使用长度位8的数做例子，写起来方便。
令$x = (0, 1, …, 7)$。

第一次奇偶二分后，得到:
$$
\left \{
\begin{array}{ll}
x_{even} & = (0, 2, 4, 6) \\
x_{odd} & = (1, 3, 5, 7) \\
x_{odd} & = x_{even} + 1
\end{array}
\right.
$$

令$x’ = (0, 1, 2, 3)$，可得：
$$ x_{even} = x’ * 2 $$

再对$x_{even}$ 做后续的奇偶二分，相当于对 $x’$做奇偶二分的基础上再$*2$。
由此递归进行，最终得到基础的一层序列$(0, 1)$。

综上所述，可得到：
$$
\left \{
\begin{array}{ll}
x_{n, left} & = x_{n-1} * 2 \\
x_{n, right} & = x_{n, left} + 1 = x_{n-1} * 2 + 1 \\
x_{n} & = (x_{n, left}, x_{n, right}) \\
x_0 & = (0, 1) \\
n & = (0, 1, …, log_2^N - 1)，其中N为序列长度
\end{array}
\right.
$$

倒位序重排

半篇文章已完，是不是已经忘记了“倒位序重排”几个字了?
倒位序是什么？跟前文解决的问题有什么关系？
一开始我以为“倒位序重排”就是“颠倒位置重新排序”，但看到英文名“Bit Reversal Permutation”之后才知道，这个位不是指“位置”，而是值“bit位”。
其实，前文的算法是求解倒位序重排的几种方法，只是没有利用“倒位”特点。

什么，还有特点？
是的，你没看错，这个序列太神奇了。下面介绍从二进制的表示上看，还有一个神奇的规律。

倒位

“位”是计算机表示信息的最小单位。
看一些倒位数例子，为方便查看，使用-代替0：

通过例子可以看出，倒位数顾名思义，是将原数按二进制表示，倒过来写，最后求得的数。
是不是想到了计算机中大端小端的概念了？通常计算机中提到的大端小端的时候，都是Byte与Byte之间的顺序关系，而不是bit与bit的位序关系，因为CPU以Byte为单位来处理，所以关注的焦点不一样。不过我也有一个未求证的理解，计算机的大端小端也描述了位序的排列方式。

倒位序

倒位序，首先描述的对象为一个序列。简单的说，对于一个数列中的每一个数，按所在的位置的倒位数重新放置，最终得到新的序列。
举个例子，有8个数，从0-7。原序列为：

可自己试试不同长度的序列，并细致的看倒位序的二进制关系，不难发现：

• 每个位置上，按序列的可表示位数 $log_2^N$ 求数的倒位数，得出的序列即为倒位数序列。
• 倒位数序列是倒位序的，可以看作“由小到大，向右进位的数列”。

得到这个特性，惊不惊喜，意不意外？
反正我是惊呆了，将序列不断的奇偶二分，居然得到了右进位的序列，并且每个得到的位置上的数是原数的倒位数。

这个特性的怎么证明呢？在网上一顿搜索“倒位序重排”，结果全是结论和代码，很难知道结论是如何得出的。也许有很多资料说明了，但我不知道用什么关键字搜到它。

证明奇偶二分得到倒位序

因为没搜到过多的资料，下面纯粹是个人的证明方式。谨慎观之。

简单证明办法

按照奇偶二分操作步骤来描述：

• 第一次奇偶二分，把数列分成了两部分。其中最低位为0的放左边，为1放右边。写作[***0 ... ***1]
• 第二次奇偶二分，在第一步的基础上二分。其中倒数第2位为0的放左边，为1放右边。写作[**00 **10 ... **01 **11]
• 第三次奇偶二分，在第二步的基础上二分。其中倒数第3位为0的放左边，为1放右边。写作[*000 *100 *010 *110 ... *001 *101 *011 *111]
• …

得出：

• 从右向左看二进制，将0放左边，将1放右边。最后就会得到一串从左向右进位的有序二进制序列。
• 原序列从右到左进位，结果序列从左到右进位。两个序列上的数只是进位表示不同，互为倒位数。

这种证明好像已经可以了，但又像是直觉层面上的证明。所以下面又尝试了复杂一点的证明办法。

倒位数性质

为了方便后续的证明理解，容我嚣张地定义一下倒位数与原数的一些性质。
令:

• BR(x,log2N)为倒位方法（“BR”是“Bit Reverse”的缩写，x是被求数，log2N可解释为序列位置可以用log2N个bit表示）。举个例子：如果按4位表示所有的数，则BR(1, 4) = BR(0001b, 4) = 1000b = 8。如果按3位表示所有的数，则BR(1, 3) = BR(001b, 3) = 100b = 4。
  为什么要假设按4位表示、或者按3位表示所有的数？前面的“倒位序”章节可以看到倒位序重排与数的大小（其实是序列长度）有关，不同的序列长度，求的倒位数不同。
• BR(x, log2N)中的x可以为序列，表示的意思是对序列中的每个元素分别求倒位数，即BR([x_1, x_2, ..., x_n], log2N) = [BR(x_1, log2N), BR(x_2, log2N), ..., BR(x_n, log2N)]。

越简单的东西越难证明，但就像1+1=2一样，这么的天经地义：

1. x = BR(BR(x, log2N), log2N)，使用相同位数表示的情况下，一个数的倒位数的倒位数就是它本身。
2. BR(2^log2N, log2N + 1) = 1，举例：3位表示的1b，倒位数位100b，而100b的倒位数位1b。
3. BR(x << 1, log2N + 1) = BR(x, log2N + 1) >> 1，一个数左移一位的倒位数，相当于它的倒位数右移一位。这里也要特别说明，数可能会溢出。比如3位表示的5，二进制位101b，当它左移时会溢出，只能用4位表示了：101b<<1 = 1010b。所以，log2N + 1是为了满足溢出的情况。
4. BR((x << 1) + 1, log2N + 1) = (BR(x, log2N + 1) >> 1) + BR(1, log2N + 1)，一个数左移一位再加1的倒位数，相当于它的倒位数右移一位加上1的倒位数。log2N + 1的解释同上，也是为了满足数溢出的情况。这个用例子解释，4bit表示的3：

   1 2 3 4 5 6 7 8 9 10

   BR((3 << 1) + 1, 3 + 1) = BR((0011b << 1) + 1, 4) = BR(0110b + 1, 4) = BR(0111b, 4) = 1110b = 0110b + 1000b = (1100b >> 1) + 1000b = (BR(BR(1100b, 4), 4) >> 1) + BR(BR(1000b, 4), 4) = (BR(0011b, 4) >> 1) + BR(0001b, 4) = (BR(3, 3 + 1) >> 1) + BR(1, 3 + 1)

5. BR(x, log2N) = BR(x, log2N + 1) >> 1，这个用例子解释，4bit表示的3：

   1 2 3 4 5 6 7

   BR(3, 4) = BR(0011b, 4) = 1100b = 11000b >> 1 = BR(BR(11000b, 5), 5) >> 1 = BR(00011b, 5) >> 1 = BR(3, 4 + 1) >> 1

6. BR(x + 2^log2N, log2N + 1) = BR(x, log2N + 1) + BR(2^log2N, log2N + 1) = BR(x, log2N + 1) + 1，log2N bit表示的一个二进制数，加上一个2 ^ log2N的数，相当于使用(log2N + 1) bit表示这个数，并置最高位为1。所以它的倒位数也相当于扩展了一个表示位后，再加1。例子说明：

   1 2 3 4 5 6 7 8

   BR(2 + 2 ^ 2, 2 + 1) = BR(010b + 100b, 3) = BR(110b, 3) = 011b = 010b + 001b = BR(BR(010b, 3), 3) + 001b = BR(010b, 3) + 1 = BR(2, 2 + 1) + 1

演绎证明

要证明奇偶二分后的序列是倒位序需要证明2点：

1. 每个位置上，按序列的可表示位数 $log_2^N$ 求数的倒位数，得出的序列即为倒位数序列。
2. 倒位数序列是倒位序的，可以看作“由小到大，向右进位的数列”。

其中第2点不需要多证明，因为如果证明了第1点，对于一个有序序列的二进制表示中，由从右向左进位的数表示，经过每个数倒位后，就变成从左向右进位。如果有点绕，可以想象一下，分别用“大端”和“小端”按位储存这个数据。

所以主要证明第1点，等价证明奇偶二分后每个位置上的数等于原位置的倒位数。

从前面用数学解释kaldi的迭代方法中可得到倒位序迭代关系。结合倒位数性质，我们只要证明最开始的迭代过程满足倒位序条件，就可以推广到无穷的情况。

为了方便数值的表示，我们先约定：

• $i_n$ 表示长度为 $N$ 的原数列，其中$n = log_2^N - 1$。也等于倒位序的位置索引序列，固定为[0, 1, 2, ..., N - 1]。
• $i_{n, left}$表示 $i_n$ 的左半部分，$i_{n, right}$ 表示 $i_n$ 的右半部分。由序列特性可知：
  $$
  \left \{
  \begin{array}{ll}
  i_{n, left} & = i_{n-1} \\
  i_{n, right} & = i_{n-1} + 2^{n}
  \end{array}
  \right.
  $$
• $x_n$ 表示长度为 $N$ 的序列，是将 $i_n$ 奇偶二分得到的序列，其中$n = log_2^N - 1$。 $x_0 = [0, 1]$。
• $x_{n, left}$表示 $x_n$ 的左半部分，$x_{n, right}$ 表示 $x_n$ 的右半部分。

结合约定，这个证明问题写成：证明$x_n = BR(i_n, n+1)$。现在开始证明吧。

后续数学公式中，使用乘2、除2代替左移1位、右移1位。

step 1:
从迭代的初始值开始验证倒位序是否满足。当序列长度位2，$log_2^N = 1$ 时：

由结果可知: $x_0 = BR(i_0, 1)$。

step 2:
当序列长度为4，$log_2^N = 2$ 时:

通过二进制可以看出，序列满足 $x_1 = BR(i_1, 2)$。但是这里要用利用递推关系来证明，才能推广到无限。
再复习一下前面序列的数学关系，有：
$$
\left \{
\begin{array}{ll}
i_{1, left} & = i_{0} \\
i_{1, right} & = i_{0} + 2^{1} \\
x_{1, left} & = x_{0} * 2 \\
x_{1, right} & = x_{0} * 2 + 1 \\
\end{array}
\right.
$$

证明左半序列，
由于$BR(i_{1, left}, 2) = BR(i_{0}, 2)$ ，
根据倒位数性质5， 得$BR(i_{0}, 2) = BR(i_{0}, 1) * 2$，
又 $\because x_0 = BR(i_0, 1)$，
$\therefore BR(i_{0}, 1) * 2 = x_0 * 2 = x_{1, left}$

证明右半序列，
由于$BR(i_{1, right}, 2) = BR(i_{0} + 2^1, 2)$ ，
根据倒位数性质6， 得$BR(i_{0} + 2^1, 2) = BR(i_{0}, 2) + 1$，
根据倒位数性质5， 得$BR(i_{0}, 2) + 1 = BR(i_{0}, 1) * 2 + 1$，
又 $\because x_0 = BR(i_0 , 1)$，
$\therefore BR(i_{0}, 1) * 2 + 1 = x_0 * 2 + 1 = x_{1, right}$

左半序列和右半序列分别得证，所以证得：
$x_1 = BR(i_1, 2)$

step 3:
将证明推广到 $n$ 与 $n-1$的关系，有：
$$
\left \{
\begin{array}{ll}
i_{n, left} & = i_{n-1} \\
i_{n, right} & = i_{n-1} + 2^{n} \\
x_{n, left} & = x_{n-1} * 2 \\
x_{n, right} & = x_{n-1} * 2 + 1 \\
x_{n-1} & = BR(i_{n-1}, n)
\end{array}
\right.
$$

证明左半序列，
由于$BR(i_{n, left}, n+1) = BR(i_{n-1}, n+1)$ ，
根据倒位数性质5， 得$BR(i_{n-1}, n+1) = BR(i_{n-1}, n) * 2$，
又 $\because x_{n-1} = BR(i_{n-1}, n)$，
$\therefore BR(i_{n-1}, n) * 2 = x_{n-1} * 2 = x_{n, left}$

证明右半序列，
由于$BR(i_{n, right}, n+1) = BR(i_{n-1} + 2^n, n+1)$ ，
根据倒位数性质6， 得$BR(i_{n-1} + 2^n, n+1) = BR(i_{n-1}, n+1) + 1$，
根据倒位数性质5， 得$BR(i_{n-1}, n+1) + 1 = BR(i_{n-1}, n) * 2 + 1$，
又 $\because x_{n-1} = BR(i_{n-1} , n)$，
$\therefore BR(i_{n-1}, n) * 2 + 1 = x_{n-1} * 2 + 1 = x_{n, right}$

左半序列和右半序列分别得证，所以证得：
$x_{n} = BR(i_{n}, n+1)$

至此证毕。

实现BR()

没有什么技巧，基本思路就是从原数的低位开始找1，找到1时，倒位数就追加为1的位，否则追加为0的位。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def bit_reverse(n, log2N):
    if n >= (2**log2N):
        print("ERR: can't use %d bit to present number %d" % (log2N, n))
        return 0

    n_br = 0
    for _ in range(log2N):
        n_br <<= 1
        if (n & 1 != 0):
            n_br = n_br + 1
        n >>= 1

    return n_br

# 改进版
def bit_reverse_inproved(n, log2N):
    if n >= (2**log2N):
        print("ERR: can't use %d bit to present number %d" % (log2N, n))
        return 0

    n_br = 0
    pos = 0
    while (n != 0):
        n_br <<= 1
        if (n & 1 != 0):
            n_br = n_br + 1
        n >>= 1
        pos += 1

    # 主要改进点是这里，免掉`bit_reverse()`中的剩余的循环
    n_br = n_br << (log2N - pos)
    return n_br

if __name__ == '__main__':
    n = 6
    log2N = 3
    print("br(%d, %d) = %d" % (n, log2N, bit_reverse(n, log2N)))
    print("br(%d, %d) = %d" % (n, log2N, bit_reverse_inproved(n, log2N)))

算法的时间花费主要在循环中。bit_reverse()固定循环log2N次。bit_reverse_inproved()的循环次数取决于二进制表示时最高位1的位置。

实现倒位序

我们可以通过使用上面的bit_reverse()函数，对序列的每一位求倒位数。
但这里介绍另一个改进版本，主要利用有序序列+1进位的特点：

• 索引为n位置的数，是在索引为n-1位置的数的基础上+1进位。
• 二进制+1进位，原数从右到左进位，倒位数是从左到右进位的。

我们先描述原数进位的计算机操作，因为这最符合我们的惯性思维：二进制从右到左，如果找到0，就将它置为1，算法结束。如果找到1，就将它置为0，然后继续从右到左找下一位。循环这个步骤。
倒位数的进位，操作方法一样，只不过方向改为从左到右。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def bit_reverse_carry(n, log2N):
    # 1的倒位数，用作进位的位置。二进制从左到右找
    br_1 = 1 << (log2N - 1)
    while ((n & br_1) != 0):
        # 将1改为0
        n = n & (~br_1)
        # 准备找下一位的位置
        br_1 >>= 1

    # 将0改为1
    n = n | br_1
    return n

def seq_bit_reverse(seq, log2N):
    # 倒位序中，首、尾的数不变，所以循环不覆盖
    for i in range(1, N - 2):
        seq[i] = bit_reverse_carry(seq[i-1], log2N)

if __name__ == '__main__':
    log2N = 4
    N = 2 ** log2N
    seq = list(range(N))
    print(seq, sep=',')

    seq_bit_reverse(seq, log2N)
    print(seq, sep=',')

算法bit_reverse_carry()之所以减少了运算复杂度，相对于bit_reverse_inproved()主要是算法循环直到遇到0就结束了，而不是循环到最高位1。
按索引位置看循环次数，当数为2的整数倍时，循环0次；索引位置为4倍+1时；循环1次，索引位置为8倍+3时，循环2次；依次类推，有：

• 有N个数都会发生0改1
• 有N/2个数发生1次1改0
• 有N/4个数发生2次1改0
• 有N/8个数发生3次1改0
• …
• 有N/N个数发生log2N次1改0。(虽然首尾的数忽略了，但这里还是算进来，方便求值)

总共为:

• 0改1次数：$N$
• 1改0次数：
  $$ ( \frac N 2 \times 1 + \frac N 4 \times 2 + \frac N 8 \times 3 + \cdots + \frac N {2^{log_2^N}} \times log_2^N ) = \sum\limits_{n = 1}^{log_2^N} \frac {N} {2^n} \times n $$

因为 $\lim_{n \rightarrow \infty} \frac {N} {2^n} \times n = 0$, 所以1改0的次数逐渐趋于常量($C$)。因此，算法时间复杂度为$O(N)$。

重排

上面的倒位序是重排的特例，因为原序列位置索引上的数，等于索引位置。
倒位序重排，简单的说，对于一个数列中的每一个数值(可以为数、字串、或其它)，按所在的位置的倒位数重新放置，最终得到新的序列。

举个例子，有8个字符，从a-h。原序列为：

重排后：

重排的代码实现也不多说了，根据前面实现倒位序来理解下面代码(主要来自几个快速傅立叶变换算法)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <stdio.h>

void reverse2(int *data,int Log2N)
{
    int i,j;
    int RevNum;
    int MaxPos,CurPos,MaxValue;
    int temp;
    MaxValue=(1<<Log2N)-1;
    MaxPos=1<<(Log2N-1);
    RevNum=0;
    
    for(i=1;i<MaxValue;i++)
    {
        
        CurPos=MaxPos;
        while((CurPos&RevNum)!=0)
        {
            RevNum=RevNum&(~CurPos);
            CurPos=CurPos>>1;
        }
        RevNum=RevNum|CurPos;

        // i相当于倒位数原数，只需要将倒位数小于原数的值交换。
        // 也可以改成大于原数的值交换。
        // 如果不加条件，两次交换相当于a<->b，然后b<->a，交换成原状态了。
        if (RevNum>i)
        {
            temp=data[RevNum];
            data[RevNum]=data[i];
            data[i]=temp;
        }
    }
}

int main(int argc, char* argv[])
{
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    int log2N = 4;
    reverse2(a, log2N);
    for (int i = 0; i < (1<<log2N); i++)
        printf("%d ", a[i]);

    printf("\n");
    return 0;
}

问题延伸

前文的奇偶二分是一种“基2(Radix 2)”的倒位序重排，其中“2”表示以2为进制。除了基2的，还有基4(Radix 4)的，基n的。

基4倒位序

基4要求序列长度是4的$n$次幂，$n$为正整数。假设序列为[0, 1, ..., N-1]，重排时，将$4n$位置的数依次放在最左边第1块，将$4n+1$的数依次放在第2块，$4n+2$放第3块，$4n+3$放第4块。然后对每块再反复做分块。
比如一个长度为16的序列：

从上表中看出4进制的倒位了吗？可以看出“倒位”的这个“位”不是1个bit位，而是以2个bit为单位了。

混合基倒位序

主要内容来自《数字信号处理教程》程佩青 第4版，章节为“N为复合数的FFT算法–混合基（多基多进制）FFT算法”。
在序列重排过程中，使用不同的步长进行分块操作。其中每个数，可以表示为多进制的数。
当我们使用10进制时，表示为：
$$
(1949)_{10} = 1\times 10^3 + 9\times 10^2 + 4\times 10^1 + 9
$$

再看混合基，当$N=r_0 r_1 … r_{L-1}$，各$r_i(i=0,1,…,L-1)$为大于1的正整数，则任一个$n<N$的正整数$n$，可以表示为多基多进制形式：
$$
(n)_{r_0 r_1 … r_{L-1}} = (n_{L-1} n_{L-2} … n_{1} n_{0})
$$

$$
\begin{array}{ll}
(n)_{10} = & (r_0 r_1 … r_{L-2})n_{L-1} + (r_0 r_1 … r_{L-3})n_{L-2} + … \\
& + (r_0 r_1)n_2 + (r_0)n_1 + n_0
\end{array}
$$

其倒位序后为：
$$
(\bar n)_{r_0 r_1 … r_{L-1}} = (n_{0} n_{1} … n_{L-2} n_{L-1})
$$

$$
\begin{array}{ll}
(\bar n)_{10} = & (r_1 r_2 … r_{L-1})n_{0} + (r_1 r_2 … r_{L-2})n_{1} + … \\
& + (r_{L-2} r_{L-1})n_{L-3} + (r_{L-1})n_{L-2} + n_{L-1}
\end{array}
$$

举例。一个长度为$N=30$的序列，使用$N=r_0 r_1 r_2 =5 \times 3 \times 2$的混合基：

测试代码(可以在jupyter notebook中运行看看)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

x = list(range(0, 30))

def rev(data, radix_list):
    if len(radix_list) == 0:
        return data

    radix = radix_list[0]
    radix_list = radix_list[1:]
    final_data = []
    for i in range(radix):
        # 按基挪位
        tmp_data = data[i::radix]
        tmp_data = rev(tmp_data, radix_list)
        final_data += tmp_data

    return final_data

# 结果序列
y = rev(x, [5, 3, 2])

import math

# 按基表示一个数
def pn(n, radix_list):
    b = []
    r = 0
    for i in range(1, len(radix_list)):
        base = math.prod(radix_list[i:])
        r = n // base
        b.append(r)
        n = n % base

    b.append(n)
    return ''.join([str(i) for i in b])

a = [pn(i, [5,3,2]) for i in x]
print(*x, sep='|')
print(*a, sep='|')

# 基也倒过来了
b = [pn(i, [2,3,5]) for i in y]
print(*y, sep='|')
print(*b, sep='|')

# 打印表格，方便md使用
xy = list(zip(x,a,y,b))
for i in xy:
    print(*i, sep='|')

总结

本文列出了暴力解法、kaldi中的迭代解法、倒位序重排，并给出了理论证明。最后介绍了基4和混合基。
在重排算法中，我更喜欢kaldi中的解法，逻辑简单，代码简单，运算高效，只不过需要空间保存倒位序列。
倒位序重排理论过程很巧妙，虽然算法时间复杂度也是$O(N)$，但有限数据下，算法效率相对弱一点点(从前面推导的时间复杂度式子可见)，并且代码逻辑有点绕。