190. Reverse Bits

Description

Reverse bits of a given 32 bits unsigned integer.

For example, given input 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?

Related problem:

Reverse Integer

Solution

Bit-manipulation, O(1), S(1)

很简单啦，遍历32位即可。注意位操作运算符的优先级很低，要用括号括起来！

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int val = 0;
        for (int i = 0; i < 32; ++i) {
            val = (val << 1) | (n & 1); // important!
            n >>= 1;                    // or n >>>= 1
        }
        return val;
    }
}

方法2：使用位操作

     /*
     * 利用高地位交换实现逆序
     * 两位一组，高低位互换，方法是（取奇数位，偶数位补0，右移1位）| （取偶数为，奇数位补0，左移1位）
     * 依次四位一组，八位一组，十六位一组，三十二位一组
     * 由于是无符号位，所以注意得是逻辑右移
     */
    public int reverseBits2(int n){
        n = ((n & 0xAAAAAAAA ) >>> 1) | ((n & 0x55555555) << 1);
        n = ((n & 0xCCCCCCCC ) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xf0f0f0f0 ) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xff00ff00 ) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xffff0000 ) >>> 16) | ((n & 0x0000ffff) << 16);
        return n;
    }