190. Reverse Bits

  • 29.5%

https://leetcode.com/problems/reverse-bits/?tab=Description

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


方法一:

我的代码实现:

对于大数,要用long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
long long res = 0;
long long cur = 1;
for(int i=0; i<32; i++){
res <<= 1;
if(cur&n)
res |= 1;
cur <<= 1;
}
return res;
}
};

注意:32位,不要使用while(n)

1
2
3
4
5
6
7
8
9
10
11
4ms, 51.95%, July 14th, 2016
https://discuss.leetcode.com/topic/10298/the-concise-c-solution-9ms
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t result = 0;
for(int i=0; i<32; i++)
result = (result<<1) + (n>>i & 1); //此处+可以换成 |
return result;
}
};

my code

注意优先级, ‘+’ > ‘>>’ > ‘&’ > ‘|’

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for(int i=0; i<32; i++){
res = (res<<1) | (n&1); // '|'可以为'+',但是如果没有括号,要注意优先级
n >>= 1;
}
return res;
}
};

my code:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for(int i=0; i<32; i++){
res <<= 1;
res |= n & 1;
n >>= 1;
}
return res;
}
};

python


1
2
3
4
5
6
7
8
9
10
11
112ms, 2.09%, July 14th, 2016
https://discuss.leetcode.com/topic/10069/python-ac-with-63ms-3lines
class Solution(object):
def reverseBits(self, n):
"""
:type n: int
:rtype: int
"""
oribin = '{0:032b}'.format(n)
reversebin = oribin[::-1]
return int(reversebin, 2)

java


1
2
3
4
5
6
7
8
9
10
11
12
13
2ms, 50.87%, July 14th, 2016
https://discuss.leetcode.com/topic/12236/concise-java-solution
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int result = 0;
for(int i=0; i < 32; ++i){
result = result << 1 | (n & 1);
n >>>= 1;
}
return result;
}
}
谢谢你,可爱的朋友。