P204 翻转整数的二进制位

描述#

这个题目说的是，给你一个 32 位整数，你要翻转它的二进制位，然后将翻转二进制位后的整数返回。

比如说，给你的整数是 32，它的二进制如下：
00000000000000000000000000100000
将 32 的二进制表示左右翻转，得到：
00000100000000000000000000000000
这个二进制表示的数字是 67108864，因此你要返回这个整数。

代码#

public class AlgoCasts {

  // Time: O(1), Space: O(1)
  public int reverseBitsOneByOne(int n) {
    int result = 0;
    for (int i = 0; i < 32; ++i) {
      result = (result << 1) | (n & 1);
      n >>= 1;
    }
    return result;
  }

  // Time: O(1), Space: O(1)
  public int reverseBitsInterchanging(int n) {
    n = (n & 0x0000FFFF) << 16 | (n & 0xFFFF0000) >>> 16;
    n = (n & 0x00FF00FF) << 8 | (n & 0xFF00FF00) >>> 8;
    n = (n & 0x0F0F0F0F) << 4 | (n & 0xF0F0F0F0) >>> 4;
    n = (n & 0x33333333) << 2 | (n & 0xCCCCCCCC) >>> 2;
    n = (n & 0x55555555) << 1 | (n & 0xAAAAAAAA) >>> 1;
    return n;
  }

}