190. Reverse Bits

Leetcode Bit Manipulation

Reverse bits of a given 32 bits unsigned integer.

Example:

Input: 43261596
Output: 964176192
Explanation: 43261596 represented in binary as 00000010100101000001111010011100, 
             return 964176192 represented in binary as 00111001011110000010100101000000.

Follow up: * If this function is called many times, how would you optimize it?

分析

这道题目没有什么特别难的地方，考察的是基本的位操作。主要过程为遍历二进制数字，依次交换头尾二进制位。关键有两点:

1. 取出二进制的任意一位
2. 改变二进制的任意一位

取出二进制的任意一位的方法是将$n$右移$i$位，和1按位与:

(n >>> i) & 1

将某一位强制转换为1:

value = value | 0x01;  //将 bit0 强制转换为1  (假设最低位称为bit0,然后是bit1, bit2...,下同）
value = value | 0x80;  //将 bit7 强制转换为1
value = value | (0x01 << N); //将 bitN 强制转换为1

将某一位强制转换为0:

value = value & 0xfe; //将 bit0 强制转换0
value = value & 0x7f; //将 bit7 强制转换成0
value = value & (~(0x01 << N)); //将 bitN 强制转换成0

如果了解这些基本操作，这道题目就非常简单了：

public int reverseBits(int n) {
    for (int i = 0; i < 16; i++) {
        int j = 31 - i;
        int lowBit = n >>> i & 1;          // 取出第i位
        int highBit = n >>> j & 1;         // 取出第32-i位
        // 交换
        if (lowBit == highBit) continue;
        if (highBit == 0) {
            n &= ~(1 << i);                 // lowBit转换为0
            n |= 1 << j;              // highBit转换为1
        } else {
            n |= 1 << i;                   // lowBit转换为1
            n &= ~(1 << j);          // highBit转换为0
        }
    }
    return n;
}

另一种方法是将反转的数字存在另一个数当中，省去了交换，依次从该二进制数中取出最低位，然后放到另一个数当中。

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result += n & 1;  // 取出第i位数字
        n >>>= 1;   
        if (i < 31) // 对于最后一位数字，不能右移
            result <<= 1;  // 结果右移一位
    }
    return result;
}

这种方法慢一些。