【CSU-1977】解题报告（二进制，位运算，读题》

原始题目

Bit-reversal Permutation

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 81
  • Solved: 27

Description

A fast Fourier transform (FFT) algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IFFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from O(n2), which arises if one simply applies the definition of DFT, to O(nlogn), where n is the data size. ——From Wikipedia

During this summer holiday, csuxushu feels so bored to learn FFT. Because FFT is a complicated algorithm, he need to apply a bit-reversal permutation to a sequence first before DFT which is a part of FFT.

In applied mathematics, a bit-reversal permutation is a permutation of a sequence of n items, where n = 2^k is a power of two. It is defined by indexing the elements of the sequence by the numbers from 0 to n − 1 and then reversing the binary representations of each of these numbers (padded so that each of these binary numbers has length exactly k). Each item is then mapped to the new position given by this reversed value.

Because all fellows in CSU(California State University ) can apply FFT, NTT or even FWT, it is a shame that he even doesn't know how to take the first step. As one of the best computer programmer in CSU, can you help him?

You may think this problem is too hard to solve. In fact, it is a piece of cake to you. Remember to see the hint :-)

Input

The first line of the input gives the number of test cases T(T≤10); T test cases follow.Each test case contains a number sequence. In each case, the first line is a number N(1≤N≤10^5), the number of elements in the following sequence.The second line is the sequence.Its length may not be exactly a power of two, so you can append some zeros to make it the minimal power of two larger than or equal to N.

Output

For each test case, output the sequence from input in bit-reversal order.

Sample Input

1
6
21 58 96 12 45 65

Sample Output

21 45 96 0 58 65 12 0

Hint

Bit-reverse Order

（图片待添加）

中文提示：可以看到，我们最终处理的系数从左至右的编号的二进制形式分别为000,100,010,110,001,101,011,111，若将其二进制反序，可得000,001,010,011,100,101,110,111，这些反序的二进制编码是从小到大排列的。也就是说，我们可以按照每个下标的二进制编码来确定处理系数的顺序。这种方法就称为位逆序置换(Bit-reversal permutation)。

Source

2017年8月月赛

Author

徐戍

题目大意

将给定序列按位反转后的顺序输出

解题思路

看中文提示和图示就能不明白，将序列顺序（从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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
const int maxn=2e5+5;

int raw[maxn];
int t;
int m,n;
int main()
{
	while(~scanf("%d",&t))
	{
		while(t--)
		{
			scanf("%d",&m);
			{
				n=0;
				memset(raw,0,sizeof(raw));
				while(pow(2,n)<m) n++;
				for(int i=0;i<m;i++)
				{
					scanf("%d",&raw[i]);
					
				}
				int len=pow(2,n);
				for(int i=0;i<len;i++)
				{
					int bit=0,b=i;
					
					for(int j=0;j<n;j++)
					{
						bit=bit|(b&1);
						b>>=1;
						bit<<=1;
					}
//					printf("bit=%d\n",bit);
					bit>>=1;
					if(i==0) printf("%d",raw[bit]);
					else printf(" %d",raw[bit]);
				}
				printf("\n");
			}
		}
	}
}

收获与反思

用二进制计算方法（按位与、按位或、左移右移），来替代pow(2,n)。否则超时 比如将序号进行位反转后再十进制化的代码。

// b为原始序列号 bit为位反转再十进制化的序列号
int bit=0,b=i;
for(int j=0;j<n;j++)
{
    bit=bit|(b&1);
    b>>=1;
    bit<<=1;
}

这一过程不要用

int bit=0,b=i;
for(int j=0;j<n;j++)
{
    if(b&1) bit+=pow(n-1-j);
    b/=2;
}
//乘方会慢很多很多