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
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
将输入转换成2进制字符串，再翻转并扩充到32位，再将此32位的二进制转为无符号整数
int 在内存中以二进制形式存储，占据32位。用一个 int 型整数 ans 来记录结果，采用移位操作，因为：1. 注意到移位操作比乘2、除2操作效率更高，2. 移位操作很好地绕开了整型运算的溢出以及符号问题。在每次循环中：ans 每次左移一位，当 n 的最低位为1时，ans 的最低位就变为1，n 每次右移一位。总共进行32次循环。
Java: 每次只需移动1位
class Solution {
public int reverseBits(int n) {
int ans = 0;
for (int i = 0; i < 32; i++) {
ans <<= 1;
if ((n & 1) == 1)
ans++;
n >>= 1;
}
return ans;
}
}
Java: 第 i 次循环移动 i 位
class Solution {
public int reverseBits(int n) {
int ans = 0;
for (int i = 0; i < 32; i++)
ans |= ((n >> i) & 1) << (31 - i);
return ans;
}
}
Python:
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
string = bin(n)
if '-' in string:
string = string[:3] + string[3:].zfill(32)[::-1]
else:
string = string[:2] + string[2:].zfill(32)[::-1]
return int(string, 2)
Python:
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
result = 0
for i in xrange(32):
result <<= 1
result |= n & 1
n >>= 1
return result
Python:
def reverseBits(n) :
res = 0
while (n > 0) :
res = res << 1
if (n & 1 == 1) :
res = res ^ 1
n = n >> 1 return res
Python:
def reverseBits2(n):
res = 0
while n > 0:
res <<= 1
res |= n & 1
n >>= 1 return res
Python: 将n的二进制表示从低位到高位的值依次取出，逆序排列得到翻转后的值。
class Solution(object):
def reverseBits(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
for i in xrange(32):
res <<= 1
res |= ((n >> i) & 1)
return res
Python: 利用Python的bin()函数
class Solution(object):
def reverseBits(self, n):
"""
:type n: int
:rtype: int
"""
b = bin(n)[:1:-1]
return int(b + '0'*(32-len(b)), 2)
C++:
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; ++i) {
if (n & 1 == 1) {
res = (res << 1) + 1;
} else {
res = res << 1;
}
n = n >> 1;
}
return res;
}
};
LeetCode中有关位操作的题：
[LeetCode] 191. Number of 1 Bits 二进制数1的个数
Repeated DNA Sequences 求重复的DNA序列
Single Number 单独的数字
Single Number II 单独的数字之二
Grey Code 格雷码
类似题目：
[LeetCode] 191. Number of 1 Bits 二进制数1的个数
[LeetCode] 7. Reverse Integer 翻转整数