2017-06-15 02:19:31 +0000   |     algorithm leetcode bit manipulation   |   Viewed times   |    

题目

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?

正常掩码法

1做掩码,一位一位地切。下面的代码是相对比较合理的切法。掩码1不变,切最低位。n往右移。切下来也放在结果最低位,然后结果往左移动。

n           01010101      right >>>  00101010
mask        00000001   &
            ------------
bit         00000001   
reverse     00000000   |
            ------------
            00000001      left  <<   00000010

代码

public class Solution {
    public int reverseBits(int n) {
        int reverse = 0;
        for (int i = 0; i < 32; i++) {
            int bit = n & 1;
            reverse <<= 1;
            reverse |= bit;
            n >>>= 1;
        }
        return reverse;
    }
}

结果

reverse-bits-1

小优化,跳过开头的多个0

如果大部分数字比较小的话,开头会有很多个0。比如这样,00000000000000000001111010011100。如果探测到剩下的都是0,就直接出结果。

代码

public class Solution {
    public int reverseBits(int n) {
        int reverse = 0;
        for (int i = 0; i < 32; i++) {
            if (n == 0) { reverse <<= (32 - i); break; }
            int bit = n & 1;
            reverse <<= 1;
            reverse |= bit;
            n >>>= 1;
        }
        return reverse;
    }
}

结果

reverse-bits-2

每次多读几位,可以预存所有可能的反转结果

每次读2位

读两位的话,只有0110的情况需要反转。1100不需要。

public class Solution {
    public int reverseBits(int n) {
        int reverse = 0;
        for (int i = 0; i < 16; i++) {
            if (n == 0) { reverse <<= (32 - 2 * i); break; }
            int bit = n & 3;
            reverse <<= 2;
            if (bit == 2) {
                reverse |= 1;
            } else if (bit == 1) {
                reverse |= 2;
            } else {
                reverse |= bit;
            }
            n >>>= 2;
        }
        return reverse;
    }
}

每次读4位

读4位就有16种可能的反转,可以都预存下来,

int[] MAP = new int[]{ 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15 };

public class Solution {
    private final int[] MAP = new int[]{ 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15 };
    public int reverseBits(int n) {
        int reverse = 0;
        for (int i = 0; i < 8; i++) {
            int bit = n & 15;
            reverse <<= 4;
            reverse |= MAP[bit];
            n >>>= 4;
        }
        return reverse;
    }
}

结果

reverse-bits-3

方法3:脑洞方法

通过多伦反转,能够反转整个数字,

abcdefgh -> efghabcd -> ghefcdab -> hgfedcba

然后反转的过程,完全用Bit Manipulation完成。在leetcode社区看到的方法。挺威武的。

代码

public class Solution {
    public int reverseBits(int n) {
        int ret=n;
        ret = ret >>> 16 | ret<<16;
        ret = (ret & 0xff00ff00) >>> 8 | (ret & 0x00ff00ff) << 8;
        ret = (ret & 0xf0f0f0f0) >>> 4 | (ret & 0x0f0f0f0f) << 4;
        ret = (ret & 0xcccccccc) >>> 2 | (ret & 0x33333333) << 2;
        ret = (ret & 0xaaaaaaaa) >>> 1 | (ret & 0x55555555) << 1;
        return ret;
    }
}

结果

reverse-bits-4