leetcode190 Reverse Bits

kyanag 發(fā)布于2019-08-06 13:28 / 2979人閱讀

摘要：思路一比特位移動(dòng)將比特位逆轉(zhuǎn)過(guò)來(lái)也就是將十進(jìn)制數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)，再?gòu)挠彝螳@得每一位上的值，再將這個(gè)值添加至結(jié)果值中。根據(jù)分治思想，逆轉(zhuǎn)個(gè)比特位等價(jià)于分別將每個(gè)比特位進(jìn)行逆轉(zhuǎn)。

題目要求

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?

你首先需要知道的事

這里涉及了十進(jìn)制和二進(jìn)制之間轉(zhuǎn)化這個(gè)知識(shí)點(diǎn)。在數(shù)學(xué)中，我們都是采用十進(jìn)制進(jìn)行計(jì)算，通俗說(shuō)就是逢十進(jìn)一。但是計(jì)算機(jī)沒(méi)有那么多類型的信號(hào)來(lái)對(duì)應(yīng)是十進(jìn)制數(shù)中的十個(gè)數(shù)字，因此采用了二進(jìn)制來(lái)進(jìn)行計(jì)算。

二進(jìn)制，也就是所謂的逢二進(jìn)一，每一位上只有兩個(gè)數(shù)字，分別是0和1。每一個(gè)十進(jìn)制都有一個(gè)唯一的二進(jìn)制數(shù)作為對(duì)應(yīng)。我們先來(lái)看一下十進(jìn)制數(shù)的計(jì)算，比如945等價(jià)于9*100+4*10+5*1，也就是9*10^2 + 4*10^1 + 5*10^0。同理我們知道，二進(jìn)制數(shù)011代表0*2^2 + 1*2^1 + 1*2^0也就是十進(jìn)制的3。這樣，我們知道如何將二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)。

那么計(jì)算機(jī)是怎么進(jìn)行計(jì)算的呢？計(jì)算機(jī)首先將十進(jìn)制數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)，再將二進(jìn)制數(shù)根據(jù)需求進(jìn)行計(jì)算。假設(shè)計(jì)算機(jī)需要計(jì)算3+6，那么轉(zhuǎn)化為二進(jìn)制就是11+110，那么計(jì)算機(jī)的計(jì)算流程如下。

1.對(duì)齊 在左側(cè)補(bǔ)零位使的兩個(gè)數(shù)字位數(shù)相同，因此就是011+110
2.逢二進(jìn)一 類似于十進(jìn)制數(shù)的逢十進(jìn)一，因此計(jì)算的結(jié)果為1001，轉(zhuǎn)化為十進(jìn)制數(shù)就是9

基于二進(jìn)制的位計(jì)算上，除去加減乘除，計(jì)算機(jī)還定義了一些其他的位運(yùn)算符

>> 將二進(jìn)制數(shù)右移，左邊根據(jù)數(shù)字的正負(fù)形補(bǔ)0或者補(bǔ)1，正數(shù)補(bǔ)0，負(fù)數(shù)補(bǔ)1。
<< 將二進(jìn)制數(shù)左移，右邊補(bǔ)0
>>> 將二進(jìn)制數(shù)右移，左邊補(bǔ)0

在這些知識(shí)的基礎(chǔ)上，我們?cè)賮?lái)看這道題目。

思路一：比特位移動(dòng)

將比特位逆轉(zhuǎn)過(guò)來(lái)也就是將十進(jìn)制數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)，再?gòu)挠彝螳@得每一位上的值，再將這個(gè)值添加至結(jié)果值中。

    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;
    }

思路二：多次計(jì)算的話利用緩存提高銷量

為了將比特位逆轉(zhuǎn)，意味著我們至少需要32次循環(huán)才能將整個(gè)遍歷完成。那么如果這個(gè)逆轉(zhuǎn)比特位方法會(huì)被調(diào)用多次的話，我們可以使用一個(gè)Map來(lái)緩存已經(jīng)遍歷過(guò)的情況。
但是，32位的重復(fù)值往往很少，因此我們可以將整數(shù)分解為多個(gè)片段存入緩存中，只要遇到重復(fù)的片段，就可以將已經(jīng)得到的結(jié)果返回給調(diào)用方。根據(jù)分治思想，逆轉(zhuǎn)32個(gè)比特位等價(jià)于分別將每8個(gè)比特位進(jìn)行逆轉(zhuǎn)。因此我們可以將長(zhǎng)度為32的unsigned int拆解成4個(gè)長(zhǎng)度為8的byte。每8個(gè)byte對(duì)應(yīng)的值可以作為片段存在緩存中，只要遇到重復(fù)的片段，就可以直接返回。

    Map cache = new HashMap();
    public int reverseBits2(int n){
        byte[] bytes = new byte[4];
        for(int i = 0 ; i<4 ; i++){
            // 獲得8位并轉(zhuǎn)換為1個(gè)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;
    }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~