190. 颠倒二进制位
2021年3月29日
两种方法，分治和-n&n
-n&n
关于这个方法，具体原理可看lowbit。
我们拿一个最大值，\(2^{31}\)
颠倒数位，观察一下，对于第\(k\)位，就相当于变成\(2^{31-k}\)
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
uint32_t maxx = 1 << 31;
while (n) {
int x = -n & n;
ans += maxx / x;
n -= x;
}
return ans;
}
};
官方解法，分治\(O(1)\)
颠倒嘛
对32位进制进行分组，显然，颠倒就相当于左右互换
那么32->16->8->4->2的顺序分上去，再并回来，就是答案了。
class Solution {
private:
const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111
public:
uint32_t reverseBits(uint32_t n) {
//左移和右移针对奇偶组
n = n >> 1 & M1 | (n & M1) << 1;
n = n >> 2 & M2 | (n & M2) << 2;
n = n >> 4 & M4 | (n & M4) << 4;
n = n >> 8 & M8 | (n & M8) << 8;
return n >> 16 | n << 16;
}
};