颠倒二进制位

示例 1：

1
2
3
4
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释:输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
	因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

1
2
3
4
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

进阶:
如果多次调用这个函数，你将如何优化你的算法？

解题思路

  1. 可以通过移位运算符来解决
    • <<：左移运算符，num<<1相当于num乘以2
    • >>：右移运算符，num>>1相当于num除以2
    • >>>：无符号右移，忽略符号位，空位都以0补齐
  2. Integer.reverse(n)

代码

位移解决

1
2
3
4
5
6
7
8
9
10
11
public int reverseBits(int n) {
    int anwser = 0;
    int i = 32;
    //类似于10进制反转的操作
    while (i-- > 0) {
        anwser <<= 1;
        anwser += n & 1;
        n >>= 1;
    }
    return anwser;
}

Integer类自带的reverse()方法

1
2
3
public int reverseBits(int n) {
    return Integer.reverse(n);
}

Integer.reverse()解析：

1
2
3
4
5
6
7
8
public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;//第一步
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;//第二步
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;//第三步
    i = (i << 24) | ((i & 0xff00) << 8) |((i >>> 8) & 0xff00) | (i >>> 24);//第四步
    return i;
}

解析如下，i，设：

$i=b_02^0+b_12^1+b_22^2+…+b_{30}2^{30}+b_{31}*2^{31}​$

  1. 计算 i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555 (&优先级大于 |)

    • (i & 0x55555555) << 1的结果为

      $b_02^1+b_22^3+b_42^5+…+b_{28}2^{29}+b_{30}*2^{31}$

    • (i>>>1) & 0x55555555的结果为

      $b_12^0+b_32^2+b_52^4+…+b_{29}2^{28}+b_{31}*2^{30}​$

    • 结果为

      $i=b_12^0+b_02^1+b_32^2+…+b_{31}2^{30}+b_{30}*2^{31}​$

      实现为$b_2b_1b_0 \to b_2b_0b_1​$、$b_5b_4b_3 \to b_5b_3b_4​$、…

  2. 计算i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333

    • (i & 0x33333333) << 2的结果

      $b_12^2+b_02^3+b_52^6+…+b_{29}2^{30}+b_{28}*2^{31}$

    • (i >>> 2) & 0x33333333的结果

      $b_32^0+b_22^1+b_72^4+…+b_{30}2^{28}+b_{30}*2^{29}​$

    • 结果为

      $i=b_32^0+b_22^1+b_12^2+…+b_{30}2^{29}+b_{29}2^{30}+b_{28}2^{31}​$

      实现为$b_2b_0b_1 \to b_0b_1b_2​$、$b_5b_3b_4 \to b_3b_4b_5​$、…

  3. 计算 i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f

    结果为：

    $i=b_72^0+b_62^1+…+b_12^6+b_02^7+…+b_{31}2^{24}+b_{30}2^{25}+…+b_{25}2^{30}+b_{24}2^{31}$

  4. 计算 i = (i << 24) | ((i & 0xff00) << 8) |((i >>> 8) & 0xff00) | (i >>> 24)

    结果为：

    $i=b_{31}2^0+b_{30}2^1+b_{29}2^2+…+b_12^{30}+b_0*2^{31}$