2016.5.16——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

1 uint32_t reverseBits(uint32_t n) {　　//uint32_t位4个字节（4*8=32），int根据操作系统不同，字节数不同，16位操作为2字节，32位操作系统为4字节，64位为8字节
2    uint32_t ret=0;
3     for(int i=0; i<32; i++) {    //为什么没有考虑将十进制转换为二进制？？ 因为用到& | << >>操作后，计算机就默认将整型转化成二进制。
4         ret<<=1;            
5         if(n&1) {
6             ret|=1;
7 }
8         n>>=1;
9 }
10     returnret;
11 }

代码2：思路二代码，复杂度为1.非常简洁，非常漂亮，膜拜大神的代码。

classSolution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);    //将32位分为16位反转，输入并不是二进制？？如何右移
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);　　 //将16位的2分为8位反转、移位   
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);    //&分为4位反转、移位
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);    //&分为2位反转、移位
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);    //&分为1位反转、移位
        returnn;
    }
};  

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：　　　 0001111010011100　0000001010010100　　

&运算右移8位：a&0xff00ff00 = 000111100000000000000010 00000000 >>右移8位: 0000000000011110 0000000000000010

a&0x00ff00ff = 00000000100111000000000010010100 <<左移8位: 10011100 0000000010010100 00000000

做 | （或）运算后b: 1001 11000001 11101001 01000000 0010

&运算右移4位：b&0xf0f0f0f0 =1001 0000 0001 00001001 00000000 0000>>右移4位: 00001001 00000001 00001001 00000000

b&0x0f0f0f0f = 0000110000001110 00000100 00000010<<左移4位: 1100 00001110 00000100 00000010 0000

做 | （或）运算后c: 11001001 1110 0001 0100 1001 00100000

&运算右移2位: c&0xcccccccc =11 0010 0011 0000 00 01 0010 00 00 0000 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函数及 测试问题

1 #include "stdafx.h"
2 #include "stdint.h"    //uint32_t的头文件
3 #include "iostream"
4 using namespacestd;
5 
6 classMyClass
7 {
8 public:
9     intReverseBits(uint32_t n)
10 {
11         uint32_t res = 0;
12         for (int i = 0; i < 32; i++)    //这个i<32,而不是i<n
13 {
14             //cout << i << endl;    //出错测试
15             res <<= 1;
16             //cout << res << endl;
17             if (n & 1)
18 {
19                 res |= 1;
20 }
21             n >>= 1;
22             //cout << n << endl;
23 }
24         returnres;
25 }        
26 };
27 
28 classSolution
29 {
30 public:
31     intreverseBits(uint32_t n)
32 {
33         n = (n >> 16 | n << 16);
34         n = ((n & 0xff00ff00) >> 8 | (n & 0x00ff00ff) << 8);
35         n = ((n & 0xf0f0f0f0) >> 4 | (n & 0x0f0f0f0f) << 4);
36         n = ((n & 0xcccccccc) >> 2 | (n & 0x33333333) << 2);
37         n = ((n & 0xaaaaaaaa) >> 1 | (n & 0x55555555) << 1);
38 
39         returnn;
40 }
41 };
42 
43 int _tmain(int argc, _TCHAR*argv[])
44 {
45 MyClass solution1;
46     //Solution solution2;
47     int m = 0;
48     int nums = 0;
49     cin >>nums;
50     m =solution1.ReverseBits(nums);
51     //m = solution2.reverseBits(nums);
52     cout << m <<endl;
53     system("pause");    //”erro：字符常量中字符过多“ 字符中应该用双引号（“”）而不是单引号（‘’）
54     return 0;
55 } 

错误：”erro：字符常量中字符过多“ 　　原因：字符中应该用双引号（“”）而不是单引号（‘’）

错误：结果值不对　　原因：第12行：这个i<32,而不是i<n