探索Integer番外篇之Integer.reverse(int

2018-10-27 本文已影响0人苏小小北

图片来源于网络,阿里巴巴与Yoox Net-A-Porter成立合资公司

1. 前言

Integer.reverse(int i)：二进制按位反转
Integer.reverseByte(int i)：二进制按byte反转

2. 源码

(1) Integer.reverse(int i)：二进制按位反转

    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_0*2^0+b_1*2^1+b_2*2^2+...+b_{30}*2^{30}+b_{31}*2^{31}$
第一步：计算 i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555( & 优先级大于 | ）
(i & 0x55555555) << 1的结果为
$b_0*2^1+b_2*2^3+b_4*2^5+...+b_{28}*2^{29}+b_{30}*2^{31}$
(i>>>1) & 0x55555555的结果为
$b_1*2^0 + b_3*2^2 + b_5*2^4+...+b_{29}*2^{28}+b_{31}*2^{30}$
所以， i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555的结果为
$\begin{eqnarray*} i = b_1*2^0 + b_0*2^1+b3*2^2+b2*2^3+...+b_{31}*2^{30}+b_{30}*2^{31} \end{eqnarray*}$
第二步：计算i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333
(i & 0x33333333) << 2的结果为
$b_1*2^2 + b_0*2^3+b5*2^6+b4*2^7+...+b_{29}*2^{30}+b_{28}*2^{31}$
(i >>> 2) & 0x33333333的结果为
$b_3*2^0 + b_2*2^1+b7*2^4+b6*2^5+...+b_{31}*2^{28}+b_{30}*2^{29}$
所以，i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333的结果为
$\begin{eqnarray*} i = b_3*2^0 + b_2*2^1 + b_1*2^2+b_0*2^2+b_7*2^4+b_6*2^5+b_5*2^6 + b_4*2^7\\ +...+b_{31}*2^{28}+b_{30}*2^{29}+b_{29}*2^{30}+b_{28}*2^{31} \end{eqnarray*}$
第三步：计算 i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
这里不一步步地计算，同理，直接给出结果，
$\begin{eqnarray*} i = &b_7*2^0&+b_6*2^1+... + b_1*2^6+b_0*2^7 \\ +...+ &b_{15}*2^8& + b_{14} * 2^9 + ...+b_9*2^{14}+b_8*2^{15}\\ +...+ &b_{23}*2^{16}&+ b_{22}*2^{17}+...+ b_{17}*2^{22}+ b_{16}*2^{23}\\ +...+&b_{31}*2^{24}&+b_{30}*2^{25}+...+b_{25}*2^{30}+b_{24}*2^{31} \end{eqnarray*}$
第四步：计算 i = (i << 24) | ((i & 0xff00) << 8) |((i >>> 8) & 0xff00) | (i >>> 24)，
i << 24的结果为
$b_7*2^{24}+b_6*2^{25}+...+ b_1*2^{30}+b_0*2^{31}$
(i & 0xff00) << 8) 的结果为
$b_{15}*2^{16}+ b_{14}*2^{17}+...+ b_{9}*2^{22}+ b_{8}*2^{23}$
(i >>> 8) & 0xff00的结果为
$b_{23}*2^{8}+ b_{22}*2^{9}+...+ b_{17}*2^{14}+ b_{16}*2^{15}$
(i >>> 24)的结果为
$b_{31}*2^0 + b_{30}*2^1 + ... + b_{25}*2^6 + b_{24}*2^7$
所以，i = (i << 24) | ((i & 0xff00) << 8) |((i >>> 8) & 0xff00) | (i >>> 24)的结果
$i = b_{31}*2^0 + b_{30}*2^1 + ... + b_1{30} + b_0{31}$

(2) Integer.reverse(int i)：二进制按位反转

原理同上，这里就不详细解释了，代码如下

    public static int reverseBytes(int i) {
        return ((i >>> 24)           ) |
               ((i >>   8) &   0xFF00) |
               ((i <<   8) & 0xFF0000) |
               ((i << 24));
    }

3.后言

4步法反转二进制数字，你学会了吗？

其他

本人也是在慢慢学习中，如有错误还请原谅、敬请指出，谢谢！