leetcode:Reverse Bits
本题目收获
移位（<< >>）， 或(|)，与（&）计算的妙用
题目：
Reverse bits of a given 32 bits unsigned integer.For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
如果看不大懂题目可以这样来看：
43261596： 00000010100101000001111010011100
964176192：00111001011110000010100101000000
这样就能看出来了，将整型转化的二进制数反转，得出反转后的二进制数。
思路：
我的思路：没有任何思路
leetcode/discuss思路：
思路1：新建一个uint32_t的数r: a: r <<= 1; r每次左移，则原二进制数的最低位就变成新数的最高位了
b: r |= n & 1; 如果原数值为1则为1，为0则为0 （可否看做字符串，不可以！！因为输入的为整型数）
c: n >>= 1; 原数值每次右移1位
思路2：将原数值32位，先分为16位反转，16位再分为8位反转，8位再分为4位反转，4位分为2位反转，2位再分为1位反转。
代码1：思路1的代码，比较简洁易懂的，但是复杂度为n
uint32_t reverseBits(uint32_t n) { //uint32_t位4个字节（4*8=32），int根据操作系统不同，字节数不同，16位操作为2字节，32位操作系统为4字节，64位为8字节
2 uint32_t ret=;
for(int i=; i<; i++) { //为什么没有考虑将十进制转换为二进制？？ 因为用到& | << >>操作后，计算机就默认将整型转化成二进制。
ret<<=;
if(n&) {
ret|=;
}
n>>=;
}
return ret;
}
代码2：思路二代码，复杂度为1.非常简洁，非常漂亮，膜拜大神的代码。
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
n = (n >> ) | (n << ); //将32位分为16位反转，输入并不是二进制？？如何右移
n = ((n & 0xff00ff00) >> ) | ((n & 0x00ff00ff) << ); //将16位的2分为8位反转、移位
n = ((n & 0xf0f0f0f0) >> ) | ((n & 0x0f0f0f0f) << ); //&分为4位反转、移位
n = ((n & 0xcccccccc) >> ) | ((n & 0x33333333) << ); //&分为2位反转、移位
n = ((n & 0xaaaaaaaa) >> ) | ((n & 0x55555555) << ); //&分为1位反转、移位
return n;
}
};
0xff00ff00:11111111000000001111111100000000 0x00ff00ff:00000000111111110000000011111111
【只有第一个8位和第三个8位不变，其他为0，右移到第二个8位和第四个8位】 【只有第二个8位和第四个8位不变，其他为0，右移到第一个8位和第三个8位】所以右移8位前两个8位相互交换位置，后两个8位会互调位置。
0xf0f0f0f0:11110000111100001111000011110000 0x0f0f0f0f:00001111000011110000111100001111
8位中的两两4位在交换位置
0xcccccccc:11001100110011001100110011001100 0x33333333:00110011001100110011001100110011
4位中的两两2位交换为值
0xaaaaaaaa:10101010101010101010101010101010 0x55555555:01010101010101010101010101010101
2位中的两两1位交换位置
例如：如题目中的
原32位（以16位分开）：0000001010010100 0001111010011100
右移16位a： 00011110 10011100 00000010 10010100
&运算右移8位：a&0xff00ff00 = 00011110 00000000 00000010 00000000 >>右移8位: 00000000 00011110 00000000 00000010
a&0x00ff00ff = 00000000 10011100 00000000 10010100 <<左移8位: 10011100 00000000 10010100 00000000
做 | （或）运算后b: 1001 1100 0001 1110 1001 0100 0000 0010
&运算右移4位：b&0xf0f0f0f0 = 1001 0000 0001 0000 1001 0000 0000 0000 >>右移4位: 0000 1001 0000 0001 0000 1001 0000 0000
b&0x0f0f0f0f = 0000 1100 0000 1110 0000 0100 0000 0010 <<左移4位: 1100 0000 1110 0000 0100 0000 0010 0000
做 | （或）运算后c: 1100 1001 1110 0001 0100 1001 0010 0000
&运算右移2位: c&0xcccccccc = 11 00 10 00 11 00 00 00 01 00 10 00 00 00 00 00 >>右移4位: 00 11 00 10 00 11 00 00 00 01 00 10 00 00 00 00
c&0x33333333 = 00 00 00 01 00 10 00 01 00 00 00 01 00 10 00 00 <<左移4位: 00 00 01 00 10 00 01 00 00 00 01 00 10 00 00 00
做 | （或）运算后d: 00 11 01 10 10 11 01 00 00 01 01 10 10 00 00 00
&运算右移2位:d&0xaaaaaaaa = 00 10 00 10 10 10 00 00 00 00 00 10 10 00 00 00 >>右移2位: 00 01 00 01 01 01 00 00 00 00 00 01 01 00 00 00
d&0x55555555 = 00 01 01 00 00 01 01 00 00 01 01 00 00 00 00 00 <<左移4位: 00 10 10 00 00 10 10 00 00 10 10 00 00 00 00 00
做 | （或）运算后e: 00 11 10 01 01 11 10 00 00 10 10 01 01 00 00 00
这是题目中的反转后的值：00 11 10 01 01 11 10 00 00 10 10 01 01 00 00 00
我的代码：带有main函数及 测试问题
#include "stdafx.h"
#include "stdint.h" //uint32_t的头文件
#include "iostream"
using namespace std; class MyClass
{
public:
int ReverseBits(uint32_t n)
{
uint32_t res = ;
for (int i = ; i < ; i++) //这个i<32,而不是i<n
{
//cout << i << endl; //出错测试
res <<= ;
//cout << res << endl;
if (n & )
{
res |= ;
}
n >>= ;
//cout << n << endl;
}
return res;
}
}; class Solution
{
public:
int reverseBits(uint32_t n)
{
n = (n >> | n << );
n = ((n & 0xff00ff00) >> | (n & 0x00ff00ff) << );
n = ((n & 0xf0f0f0f0) >> | (n & 0x0f0f0f0f) << );
n = ((n & 0xcccccccc) >> | (n & 0x33333333) << );
n = ((n & 0xaaaaaaaa) >> | (n & 0x55555555) << ); return n;
}
}; int _tmain(int argc, _TCHAR* argv[])
{
MyClass solution1;
//Solution solution2;
int m = ;
int nums = ;
cin >> nums;
m = solution1.ReverseBits(nums);
//m = solution2.reverseBits(nums);
cout << m << endl;
system("pause"); //”erro：字符常量中字符过多“ 字符中应该用双引号（“”）而不是单引号（‘’）
return ;
}
错误：”erro：字符常量中字符过多“ 原因：字符中应该用双引号（“”）而不是单引号（‘’）
错误：结果值不对 原因：第12行：这个i<32,而不是i<n