题目
颠倒给定的 32 位无符号整数的二进制位。
分析
按位颠倒
我们从低到高依次取给定数的每一个二进制位$i$，将其放置在$31 - i$的位置上即可。
代码
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
for (size_t i = 0; i < 32 && n > 0; ++i, n >>= 1)
{
ans = ans | ((n & 1) << (31 - i));
}
return ans;
}
};
|
时间复杂度：
因为每次$n$都减小为原来的一半，所以时间复杂度为$O(logn).$
空间复杂度：
$O(1).$
分治
分治只需要分别将左半和右半颠倒，然后左半和右半在整体颠倒即可。采用自底向上的方式，首先两两一组，交换相邻的两位，然后四个四个一组，交换相邻的左半和右半，依次类推。
编码的时候，我们采用掩码的技巧进行编码，方便我们进行颠倒操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
const uint32_t M1 = 0x55555555;
const uint32_t M2 = 0x33333333;
const uint32_t M3 = 0x0f0f0f0f;
const uint32_t M4 = 0x00ff00ff;
public:
uint32_t reverseBits(uint32_t n) {
n = (n >> 1) & M1 | (n & M1) << 1;
n = (n >> 2) & M2 | (n & M2) << 2;
n = (n >> 4) & M3 | (n & M3) << 4;
n = (n >> 8) & M4 | (n & M4) << 8;
return (n >> 16) | (n << 16);
}
};
|
时间复杂度：$O(1).$
空间复杂度：$O(1)$.