leetcode 190. Reverse Bits

2017-08-07

题意

反转一个无符号int型二进制数字。

比如输入43261596，它的二进制码是++00000010100101000001111010011100++
返回964176192（因为它的二进制码是++00111001011110000010100101000000++）

我的代码

思路比较简单，就不解释，直接上代码。

我这份代码过不了案例2147483648，这个数在java中是超过了int类型的范围的。所以必须用位移操作符来进行。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        if(n==1) return Integer.MIN_VALUE;
        int power = 31;
        int result = 0;
        while(n>0){
            if(n%2!=0){
               result += Math.pow(2,power);
            }
            n = n/2;
            power--;
        }
        return result;
    }
}

大神代码

考虑到java中没有unsigned数字，必须采用位移操作。

每个数看成32位。

n&1得到数的最后一位。

result每次累加最后一位，然后自己左移，移动31次，不然会溢出了

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result += n & 1;
        n >>>= 1;   // CATCH: must do unsigned shift
        if (i < 31) // CATCH: for last digit, don't shift!
            result <<= 1;
    }
    return result;
}

这段代码是上段代码的简化。把最后一次操作符放到了return当中了。

public int reverseBits(int n) {
    int res = 0;
    for(int i = 0; i < 31; ++i, n >>>= 1)
        res = ( res + (n & 1) ) << 1;
    return res + (n & 1);
}

神级代码。位操作我反正看不懂。

public class Solution {
    public int reverseBits(int n) {
        n = (n >>> 16) | (n << 16); 	// 前16 bits 与 后16 bits 交换
    	n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8); 	// 前8 bits 与 后8 bits 交换
    	n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4); 	// 前4 bits 与 后4 bits 交换
    	n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2); 	// 前2 bits 与 后2 bits 交换
    	n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1); 	// 前1 bit  与 后1 bit  交换
    	return n;
    }
}

通过这道题学到无符号右移操作’>>>‘，右移高位始终用0补位。’>>’右移操作，如果数是负数用1补高位，正数高位用0补高位。负数在计算机中用补码表示。比如-2的二进制码是(1111111111111111111111111111110)。