LeetCodeDay31 —— 颠倒二进制位★★

190. 颠倒二进制位

描述

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

示例

输入: 43261596
输出: 964176192
解释: 43261596 的二进制表示形式为 00000010100101000001111010011100 ，
     返回 964176192，其二进制表示形式为 00111001011110000010100101000000 。

进阶:
如果多次调用这个函数，你将如何优化你的算法？

思路

1. 每次取出1位加到结果上去，注意0对应位置31, 1对应位置30, i对应位置31-i
2. 将上述思路的加法操作转换为移位操作，通过 | 操作将对应数值附上去，然后每次向左移位1次，再去或上新的数值，最终 i 左移到 31 - i 的位置上。
3. 基于旋转的思想，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;
  }
};