07
04/2015
[LeetCode] Reverse Bits
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 as00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?
解题思路：
通过移位来计算。下面是代码：
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t result=0;
int size = sizeof(uint32_t)*8;
for(int i=0; i<size; i++){
result = result << 1;
result += n%2;
n=n>>1;
}
return result;
}
};注意到，倘若n是一个很小的数，根本就不需要循环size位，若n右移一定位后为0，便可以跳出循环。result再左移剩下的位数即可。下面是优化后的代码：
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t result=0;
int size = sizeof(uint32_t)*8;
int i=0; //已经移动的位数
while(n!=0){
result = result << 1;
result += n%2;
n=n>>1;
i++;
}
result <<= size - i;
return result;
}
};二次刷题（2015-08-06）
注意sizeof只是字节数，还需要乘以8才是位数。
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t result = 0;
for(int i = 0; i<sizeof(uint32_t)*8; i++){
result = result << 1;
result += n & 0x1;
n = n>>1;
}
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Reverse Bits
0 条评论