颠倒二进制位

颠倒二进制位

这道题出自LeetCode，题目如下：

颠倒给定的 32 位无符号整数的二进制位。

示例1 :

**输入：**00000010100101000001111010011100
**输出：**00111001011110000010100101000000

示例2 :

**输入：**11111111111111111111111111111101
**输出：**10111111111111111111111111111111

示例3 :

**输入：**n = 00000010100101000001111010011100
**输出：**964176192 (00111001011110000010100101000000)

示例4 :

**输入：**n = 11111111111111111111111111111101
**输出：**3221225471 (10111111111111111111111111111111)

这道题的意思很简单，而且有一种在O(1)时间内计算出结果的巧妙解法。要想颠倒32位二进制位，我们可以利用分而治之的思想进行考虑。首先，颠倒这个数的前16位二进制位和后16位二进制位。这个是很容易做到的。颠倒之后，我们发现，如果这两个16位二进制位内部已经是颠倒之后的，那么问题实际上就解决了。那么，对于每一个16位的二进制数，我们可以重复之前类似的操作，去颠倒它的前8位和后8位。这里有个trick，即对于32位的二进制数，可以分成4组，其中奇数组部分和偶数组部分进行颠倒，这样一步就可以完成颠倒2个16位二进制数的前后8位的操作。类似地，对于颠倒之后的每个8位二进制数，要继续去做颠倒前4位和后4位，对应的就是把32位的二进制数分成8组，奇数组和偶数组颠倒。以此类推，直到把32位的二进制数分成32组，颠倒完为止。最终通过的代码如下：

class Solution {
public:uint32_t reverseBits(uint32_t n) {const uint32_t M1 = 0x55555555;  // 01010101010101010101010101010101const uint32_t M2 = 0x33333333;  // 00110011001100110011001100110011const uint32_t M4 = 0x0f0f0f0f;  // 00001111000011110000111100001111const uint32_t M8 = 0x00ff00ff;  // 00000000111111110000000011111111const uint32_t M16 = 0x0000ffff; // 00000000000000001111111111111111n = ((n & M16) << 16) | ((n >> 16) & M16);n = ((n & M8) << 8) | ((n >> 8) & M8);n = ((n & M4) << 4) | ((n >> 4) & M4);n = ((n & M2) << 2) | ((n >> 2) & M2);n = ((n & M1) << 1) | ((n >> 1) & M1);return n;}
};