190. 颠倒二进制位
描述
示例
输入: 43261596
输出: 964176192
解释: 43261596 的二进制表示形式为 00000010100101000001111010011100 ，
返回 964176192，其二进制表示形式为 00111001011110000010100101000000 。
进阶:
如果多次调用这个函数，你将如何优化你的算法？
思路
- 每次取出1位加到结果上去，注意0对应位置31, 1对应位置30, i对应位置31-i
- 将上述思路的加法操作转换为移位操作，通过 | 操作将对应数值附上去，然后每次向左移位1次，再去或上新的数值，最终 i 左移到 31 - i 的位置上。
- 基于旋转的思想，32位数从16开始成对旋转，然后是8、最后到1。(参考)
class Solution_190_01 {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; ++i) {
if ((n >> i) & 0x01) {
res += (0x01 << (31 - i));
}
}
return res;
}
};
class Solution_190_02 {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; ++i) {
res <<= 1;
res |= n & 0x01;
n >>= 1;
}
return res;
}
};
class Solution_190_03 {
public:
uint32_t reverseBits(uint32_t n) {
n = (n >> 16) | (n << 16);
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
return n;
}
};
