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).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

 

题目意思将10进制转换成二进制位,然后全部reverse,进而返回所有位颠倒后转换的10进制数字,看上去挺容易,python里试了试

>>> a = 10
>>> bin(a)
'0b1010'
>>> bin(a).replace('0b', '')
'1010'
>>> bin(a).replace('0b', '')[::-1]
'0101'
>>> '0b' + bin(a).replace('0b', '')[::-1]
'0b0101'
>>> int('0b' + bin(a).replace('0b', '')[::-1], 2)
5

的确很容易的说

第一次提交

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        return int('0b' + bin(n).replace('0b', '')[::-1], 2)

给出的返回结果

Submission Result: Wrong Answer

Input:	           1 (00000000000000000000000000000001)
Output:	           1 (00000000000000000000000000000001)
Expected:	  2147483648 (10000000000000000000000000000000)

输入1试试,看哪一步出错

>>> a = 1
>>> bin(a)
'0b1'
>>> bin(a).replace('0b', '')
'1'
>>> bin(a).replace('0b', '')[::-1]
'1'

原因是转换成二进制之后,高位的0都自动去掉了,导致进行reverse的时候,原本低位的数应该在更高位;比如对于10进制数1,换成二进制应该是0b00…01,前面31个0,颠倒之后应该是0b10…00,后面31个0,而这里由于前面31个0去掉了,导致颠倒后1还是在最低位

实际上要想计算颠倒bit后的十进制数字,可以这么倒推:

计算十进制,也就是将二进制位一位一位乘以2的位-1次幂,只不过这个位次是倒过来的;那么对于颠倒前的二进制位,这个位次正好是顺着的,也就是说,根本没必要去颠倒原来数字的二进制位,只需要将原本数字二进制位顺序地计算十进制,但是有个前提,位数不够的,前面补满0

比如n = 10,二进制0b1010,实际上应该是:

0b00……1010,前面有28个0,进行颠倒之后变成0b010100……0000,后面有28个0

最后结果就是0 + 1 * 2 ^ 28 + 0 + 1 * 2 ^ 30 + 0,更直观一点就是

0 + 1 * 2 ^ (32 – 4) + 0 * 2 ^ (32 – 3) + 1 * 2 ^ (32 – 2) + 0 * 2 ^ (32 – 1)

4就是n转换成二进制的长度,如此看来值需要得到二进制位长度,颠倒后二进制转换成十进制,其实也就是颠倒前二进制倒着转换成十进制,倒着意思就是从高位到低位依次乘以2^0, 2^1……,一直到2^31,这样就很好遍历了

第二次提交

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        a = bin(n).replace('0b', '')
        i = 32 - len(a)
        sum = 0
        for b in a:
            sum += int(b) * int(math.pow(2, i))
            i += 1
        return sum

结果通过

600 / 600 test cases passed.
Status: Accepted
Runtime: 76 ms

发表回复