证明：将n（n为2的幂）个点的位反转环划分为长为j（2的幂）的连续片段，这些片段都是次序等价的（分布式算法）

这个证明让我花了好大力气（可能是我太笨了，貌似同学都做出来了，也没人说这个难），开始想证明，似乎不会，就想偷懒上网找答案，找不到，又回来想……

我觉得关键在于把规律看出来，写个程序，打印几个例子看一看，我就是把16个元素的打印出来，找到规律，虽然说找到规律要证明也要一点工夫，但是，找到规律就是找到了努力的方向，成功就不远了

位反转：把一个数的二进制表示倒过来（最低位换到最高位，次低位换到次高位……），比如6的二进制表示为110，反转后是011，即6对应的位反转数为3。对位反转应该要限制二进制表示的位数，因为如果把6表示成4位二进制0110，反转后是6,而不是3.

（这里位反转数是为了称呼方便自造的，Google了一下，似乎没有位反转数这个称呼，也没有bit reverse number的wiki之类，倒是有人以这个为关键词搜索）

举例：

[0..15]对应的位反转数组为0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

顺便贴一下代码，当然，这远远不是最优的，甚至也不算简洁，说不定还有bug，只供参考

View Code

#include <stdio.h>
//翻转a，翻转的范围为begin到end
unsigned rev(unsigned a, int begin, int end)
{
    for(unsigned i = (1 << begin), j = 1 << end;
            i < j; i <<= 1, j >>= 1){
        //i用来测试低位，j用来测试对称的高位
        if ((a & i) && !(a & j) || !(a & i) && (a & j)) {
            //如果低位为0，高位为1；或者低位为1，高位为0，则需要交换
            a ^= i, a ^= j;//高位翻转，低位也翻转（等同于交换）
        }
    }
    return a;
}
int main(int argc, const char *argv[])
{
    int begin = 0, end = 3;
    for (unsigned int i = 0; i < 16; i++) {
        printf("%u, ", rev(i, begin, end));
    }
    return 0;
}

(次)序等价：两个数组A[1..L],B[1..L](假设每个数组中的元素各不相同)，对每个i,j，A[i]<A[j]当且仅当B[i]<B[j]

例如：

6，3，5，9与3，1，2，5是次序等价的

位反转环：环上有n个处理器P(0),P(1)...P(n-1)，第k个处理器的id为rev[k]（k对应的位反转数）

下图是8个处理器的位反转环