leetcode190.Reverse Bits

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
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?

你首先需要知道的事

这里涉及了十进制和二进制之间转化这个知识点。在数学中，我们都是采用十进制进行计算，通俗说就是逢十进一。但是计算机没有那么多类型的信号来对应是十进制数中的十个数字，因此采用了二进制来进行计算。

二进制，也就是所谓的逢二进一，每一位上只有两个数字，分别是0和1。每一个十进制都有一个唯一的二进制数作为对应。我们先来看一下十进制数的计算，比如945等价于9*100+4*10+5*1，也就是9*10^2 + 4*10^1 + 5*10^0。同理我们知道，二进制数011代表0*2^2 + 1*2^1 + 1*2^0也就是十进制的3。这样，我们知道如何将二进制数转化为十进制数。

那么计算机是怎么进行计算的呢？计算机首先将十进制数转化为二进制数，再将二进制数根据需求进行计算。假设计算机需要计算3+6，那么转化为二进制就是11+110，那么计算机的计算流程如下。

1.对齐 在左侧补零位使的两个数字位数相同，因此就是011+110
2.逢二进一 类似于十进制数的逢十进一，因此计算的结果为1001，转化为十进制数就是9

基于二进制的位计算上，除去加减乘除，计算机还定义了一些其他的位运算符

>> 将二进制数右移，左边根据数字的正负形补0或者补1，正数补0，负数补1。
<< 将二进制数左移，右边补0
>>> 将二进制数右移，左边补0

在这些知识的基础上，我们再来看这道题目。

思路一：比特位移动

将比特位逆转过来也就是将十进制数转化为二进制数，再从右往左获得每一位上的值，再将这个值添加至结果值中。

1
2
3
4
5
6
7
8
9
10
11
public int reverseBits(int n) {
    //获得最后一位的值
    int mask = 1;
    int result = 0;
    for(int i=0 ; i<32 ; i++){
        result <<= 1;
        result |= (n & mask);
        n >>= 1;
    }
    return result;
}

思路二：多次计算的话利用缓存提高销量##

为了将比特位逆转，意味着我们至少需要32次循环才能将整个遍历完成。那么如果这个逆转比特位方法会被调用多次的话，我们可以使用一个Map来缓存已经遍历过的情况。
但是，32位的重复值往往很少，因此我们可以将整数分解为多个片段存入缓存中，只要遇到重复的片段，就可以将已经得到的结果返回给调用方。根据分治思想，逆转32个比特位等价于分别将每8个比特位进行逆转。因此我们可以将长度为32的unsigned int拆解成4个长度为8的byte。每8个byte对应的值可以作为片段存在缓存中，只要遇到重复的片段，就可以直接返回。

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
Map<Byte, Integer> cache = new HashMap<Byte, Integer>();
public int reverseBits2(int n){
    byte[] bytes = new byte[4];
    for(int i = 0 ; i<4 ; i++){
        // 获得8位并转换为1个byte
        bytes[i] = (byte) ((n>>>(i*8)) & 0xff);
    }
    int result = 0;
    for(int i = 0 ; i<4 ; i++){
        result += reverseByte(bytes[i]);
        if(i<3) result<<=8;
    }
    return result;
}

public int reverseByte(byte b){
    Integer value = cache.get(b);
    if(value != null) return value;
    value = 0;
    for(int i = 0 ; i<8 ; i++){
        value += ((b>>>i) & 1);
        if(i<7) value <<= 1;
    }
    cache.put(b, value);
    return value;
}