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
