Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author: goal00001111
Date: 17-12-08 09:24
Description:
描述 Description
给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。
我们称这个二进制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。
试问这个新的数是多少（用十进制表示）。
例如，数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），
其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，
我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。
输入格式 Input Format
一个小于2^32的正整数
输出格式 Output Format
将新的数输出
样例输入 Sample Input
1314520
样例输出 Sample Output
249036820
题目分析：
这是一道考查位运算的题目，如果我们对位运算足够熟悉的话，主要代码可以简单到只有一行。
我将依次分析常规方法和巧妙利用位运算的方法。
方法一：常规方法是直接根据题意，模拟十进制和二进制的转换过程。方法虽然繁琐，
但是却能够帮助我们加深对进制转换的理解，特别是十进制转换为二进制，利用了位运算中的与运算，得到各位的值，很巧妙。
方法二：使用了一定的数学分析，注意到n的低16位数low = n % (2^16); 高16位数high = n - low;
然后将low*(2^16)就变成高16位，而high / (2^16)就变成了低16位，从而完成转换。
方法三：位运算的巧妙应用，分别将n左右移位16位，然后相加就行了，则执行(n << 16) | (n >> 16)即可。
说明：
算法思想：直接模拟或数学分析。
数据结构：数组。
时间复杂度：O(1);;
空间复杂度：方法一为O(32)，方法二，三不需要辅助空间;
程序语言：分别用c++和pascal实现。
附注：分别提供了直接模拟和数学分析等三者实现方法。
有关位运算的详细知识请参考：Matrix67的博客http://www.matrix67.com/blog/archives/263
c++代码：
#include<iostream>
using namespace std;
unsigned long long Simulate(unsigned long long n);//直接模拟方法
unsigned long long Analyse(unsigned long long n); //数学分析方法1：间接移位
unsigned long long Shift(unsigned long long n); //数学分析方法2：直接移位
int main()
{
unsigned long long n;
cin >> n;
cout << Analyse(n) << endl;
cout << Simulate(n) << endl;
cout << Shift(n) << endl;
system("pause");
return 0;
}
//直接模拟方法：先将十进制数转换成二进制，高低换位后再换回来
unsigned long long Simulate(unsigned long long n)
{
unsigned long long a[32] = {1};//存储2^n(n=0,1,2,...,31)
int b[32] = {0}; //用来存储二进制数
for (int i=1; i<32; i++)//计算并存储2^n(n=0,1,2,...,31)
{
a[i] = a[i-1] * 2;
}
for (int i=0; i<32; i++) //转化成二进制数
{
b[31-i] = (a[i] & n) != 0;
}
for (int i=0; i<16; i++) //高低换位
{
int temp = b[i];
b[i] = b[i+16];
b[i+16] = temp;
}
n = 0;
for (int i=0; i<32; i++)//转化成十进制数
{
n += a[i] * b[31-i];
}
return n;
}
//数学分析方法：分别取高低16位后，进行移位运算换位
unsigned long long Analyse(unsigned long long n)
{
const unsigned long long MAX = 65536; //MAX = 2^16
unsigned long long dest, high, low;
low = n % MAX; //取低16位数
high = n - low;//取高16位数
dest = low * MAX;//将低16位数左移16位，即乘以2^16
dest += high / MAX;//将高16位数右移16位，即除以2^16
return dest;
}
//数学分析方法：直接进行移位运算换位
unsigned long long Shift(unsigned long long n)
{
return (n << 16) | (n >> 16);
}
PASCAL代码：
PROGRAM P1201 (INPUT, OUTPUT);
VAR
n : longword;
{数学分析方法：分别取高低16位后，进行移位运算换位}
FUNCTION Analyse(n : longword):longword;
const
MAX = 65536; {MAX = 2^16}
var
dest, high, low : longword;
begin
low := n mod MAX; {取低16位数}
high := n - low; {取高16位数}
dest := low * MAX; {将低16位数左移16位，即乘以2^16}
dest := dest + high div MAX; {将高16位数右移16位，即除以2^16}
Analyse := dest;
end; {Analys}
{数学分析方法：直接进行移位运算换位}
FUNCTION Shift(n : longword):longword;
begin
Shift := (n shr 16) or (n shl 16);
end; {Shift}
{直接模拟方法：先将十进制数转换成二进制，高低换位后再换回来}
FUNCTION Simulate(n : longword):longword;
var
a : array [1..32] of longword; {存储2^n(n=0,1,2,...,31)}
b : array [1..32] of integer; {用来存储二进制数}
i, temp : integer;
begin
a[1] := 1;
for i:=2 to 32 do {存储2^n(n=0,1,2,...,31)}
a[i] := a[i-1] * 2;
for i:=1 to 32 do {转化成二进制数}
b[33-i] := ord((a[i] and n) <> 0);
for i:=1 to 16 do {高低换位}
begin
temp := b[i];
b[i] := b[i+16];
b[i+16] := temp;
end;
n := 0;
for i:=1 to 32 do {转化成十进制数}
n := n + a[i] * b[33-i];
Simulate := n;
end; {Simulate}
BEGIN {main}
read(n);
writeln(Analyse(n));
writeln(Simulate(n));
writeln(Shift(n));
readln;
END.