问题：
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).
Follow up:
If this function is called many times, how would you optimize it?Related problem:
解决：
① 目标：将二进制串反转，原数不断右移取出最低位，赋给新数的最低位后新数再不断左移。
public class Solution { // 2ms
// you need treat n as an unsigned value public int reverseBits(int n) { int res = 0; for (int i = 0;i < 32 ;i ++,n >>= 1) { res = res << 1 | (n & 1); //将结果左移然后将最低位取出赋值给新的数（移位运算符优先于|） } return res; } }更好理解一点的写法
public class Solution { //2ms
// you need treat n as an unsigned value public int reverseBits(int n) { int res = 0; for (int i = 0;i < 32 ;i ++ ) { res = (res << 1) + (n & 1); n = n >> 1; } return res; } }② 分段相或法：根据Java标准的Integer.reverse()源码。将数字的位按照整块整块的翻转，例如32位分成两块16位的数字，16位分成两个8位进行翻转，这样以此类推直到只有一位。
public class Solution{ //2ms
public int reverseBits(int n) { int res = n; res = res >>> 16 | res << 16; //交换前后两个双字节 res = (res & 0xff00ff00) >>> 8 | (res & 0x00ff00ff) << 8; //交换相邻的两个字节 res = (res & 0xf0f0f0f0) >>> 4 | (res & 0x0f0f0f0f) << 4; //交换每8位中的前四位和后四位 res = (res & 0xcccccccc) >>> 2 | (res & 0x33333333) << 2; //交换每4位中的前两位和后两位 res = (res & 0xaaaaaaaa) >>> 1 | (res & 0x55555555) << 1; //交换每两位 return res; } }上面的16进制数字中:
0xff00ff00 = 1111 1111 0000 0000 1111 1111 0000 0000
0x00ff00ff = 0000 0000 1111 1111 0000 0000 1111 1111
0xf0f0f0f0 = 1111 0000 1111 0000 1111 0000 1111 0000
0x0f0f0f0f = 0000 1111 0000 1111 0000 1111 0000 1111
0xCCCCCCCC = 1100 1100 1100 1100 1100 1100 1100 1100
0x33333333 = 0011 0011 0011 0011 0011 0011 0011 0011
0xAAAAAAAA = 1010 1010 1010 1010 1010 1010 1010 1010
0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
/* 0000 0010 1001 0100 0001 1110 1001 1100 0001 1110 1001 1100 0000 0010 1001 0100 //每16位交换 1001 1100 0001 1110 1001 0100 0000 0010 //每8位交换 1100 1001 1110 0001 0100 1001 0010 0000 //每4位交换 0011 0110 1011 0100 0001 0110 1000 0000 //每2位交换 0011 1001 0111 1000 0010 1001 0100 0000 //每1位交换 */
③ Follow Up：如果该方法被大量调用，或者用于处理超大数据（Bulk data）时有什么优化方法？discuss
大规模数据时算法最基本的优化方法。其实道理很简单，反复要用到的东西记下来就行了，所以我们用Map记录之前反转过的数字和结果。更好的优化方法是将其按照Byte分成4段存储，节省空间。。。。。
public class Solution{ //7ms
private final Map<Byte, Integer> map = new HashMap<Byte, Integer>(); public int reverseBits(int n) { byte[] bytes = new byte[4]; for (int i = 0; i < 4; i ++) // convert int into 4 bytes bytes[i] = (byte)((n >>> 8 * i) & 0xFF); int result = 0; for (int i = 0; i < 4; i ++) { result += reverseByte(bytes[i]); // reverse per byte if (i < 3) result <<= 8; } return result; } private int reverseByte(byte b) { Integer value = map.get(b); // first look up from map if (value != null) return value; value = 0; // reverse by bit for (int i = 0; i < 8; i ++) { value += ((b >>> i) & 1); if (i < 7) value <<= 1; } map.put(b, value); return value; } }