190. 顛倒二進(jìn)制位

題目

方法1：
利用位運(yùn)算來操作，

仔細(xì)看下代碼，看看怎么做的：

class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        mi = 31
        while n:
            # 注意這里&表示與運(yùn)算，比直接對2求余要算的更快
            ans += (n&1)<<mi
            mi -= 1
            # 這里使用>>右移運(yùn)算，比直接對2整除算的更快
            n = n>>1
        return ans

方法2：
分治的方法
我們可以通過以下步驟實(shí)現(xiàn)該算法：
首先，我們將原來的 32 位分為 2 個 16 位的塊。
然后我們將 16 位塊分成 2 個 8 位的塊。
然后我們繼續(xù)將這些塊分成更小的塊，直到達(dá)到 1 位的塊。
在上述每個步驟中，我們將中間結(jié)果合并為一個整數(shù)，作為下一步的輸入。
看一下，下面的代碼中的位運(yùn)算，左移右移和或操作相結(jié)合，剛好可以顛倒一個二進(jìn)制數(shù)：

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        n = (n >> 16) | (n << 16)
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
        return n