电子商务平台(网站)建设方式/建一个app平台的费用多少

蝴蝶操作和Rader排序

蝴蝶操作的定义：

 

 

 

 

雷德(Rader)算法 (Gold Rader bit reversal algorithm)

按自然顺序排列的二进制数，其下面一个数总是比其上面一个数大1，即下面一个数是上面一个数在最低位加1并向高位进位而得到的。而倒位序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位进位而得到。

I、 J都是从0开始，若已知某个倒位序J，要求下一个倒位序数，则应先判断J的最高位是否为0，这可与k=N/2相比较，因为N/2总是等于100..的。如 果k>J，则J的最高位为0，只要把该位变为1（J与k=N/2相加即可），就得到下一个倒位序数；如果K<=J，则J的最高位为1，可将最 高位变为0（J与k=N/2相减即可）。然后还需判断次高位，这可与k=N\4相比较，若次高位为0，则需将它变为1（加N\4即可）其他位不变，既得到 下一个倒位序数；若次高位是1，则需将它也变为0。然后再判断下一位。。。。

 

原来的序号             0      1       2       3      4        5       6       7

原来的二进制表示 000  001   010   011   100   101   110   111

现在的序号             0      4        2        6        1        5        3      7

现在的二进制表示  000  100    010    110    100    101    011   111

从高位到低位依次判断其是否为1，为1将其变位0，若这一位为0，将其变位1，即可得到倒序数。若倒序数小于顺序数，进行换位，否则不变，防治重复交换，变回原数。

伪码:

for i = 0 ... n − 2 dok = n/2if i < j thenswap g(i) and g(j)end ifwhile k ≤ j doj ⇐ j − kk ⇐ k/2end whilej ⇐ j + k
end for

 

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define MAXN 256
int reversal[MAXN] = {0}; // 存放二进制反转下标
int limit=1; // 数组2次幂上限
int bit = 0; // 二进制位数
void swap(int *a, int *b)
{int tmp;tmp = *a;*a = *b;*b = tmp;/** int *tmp;* tmp=a;* a=b;* b=tmp;*/return;
}/** 数组根据元素下标进行二进制反转.* 将下标为当前下标折半的数组元素值右移一位,如果是奇数,则最高位加1.*/
void rader_bit_reversal(int *array, int size)
{while(limit<size) limit<<=1, ++bit;printf("%d\n", bit);for(int i=0;i<size;i++){reversal[i]= ( reversal[i>>1]>>1 )| ( (i&1)<<(bit-1) ) ;if(i<reversal[i])swap(&array[i],&array[reversal[i]]);//求出要迭代的序列
    }//for(int i=0;i<size;i++)for(int idx = 0; idx < size; ++idx)printf("%d ", array[idx]);return;
}int main(void)
{// 整体思想:倒位序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位进位而得到。int array[] = { 0, 1, 2, 3, 4, 5, 6, 7 };int i, j, k;int N = sizeof(array)/sizeof(array[0]);int temp;j = 0; // 反转下标for (i = 0; i < N - 1; i++) {// 若倒序数i小于顺序数j，进行换位，否则不变，防治重复交换，变回原数。if (i < j) {temp = array[i];array[i] = array[j];array[j] = temp;}// k代表以二进制数表示的数组array元素个数(必须是2的整数次幂的倍数)的最高位的1.k = N >> 1;// 若已知某个倒位序J，要求下一个倒位序数，则应先判断J的最高位是否为0，这可与k=N/2相比较，因为N/2总是等于100..的。如 果k>J，则J的最高位为0，只要把该位变为1（J与k=N/2相加即可），就得到下一个倒位序数;如果K<=J，则J的最高位为1，可将最 高位变为0（J与k=N/2相减即可）。然后还需判断次高位，这可与k=N\4相比较，若次高位为0，则需将它变为1（加N\4即可）其他位不变，既得到 下一个倒位序数；若次高位是1，则需将它也变为0。然后再判断下一位。。。。while (k <= j) {j = j - k;k >>= 1;}j = j + k;}for (i = 0; i < N; i++)printf("%d ", array[i]);printf("\n");int array2[] = { 0, 1, 2, 3, 4, 5, 6, 7 };int size = sizeof(array2)/sizeof(array2[0]);rader_bit_reversal(array2, size);return 0;
}