JDK Integer.reverse 算法实现分析

1 JDK Integer.reverse 算法源码如下

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;
}

　　

2 算法分析如下：

首先观察一个通用的数组A[a0,a1,a2...an]，则其反转数组A`为[an,...a2,a1,a0]

可以看出，A`的前半部分集合元素A`start为[an/2,...an]，后半部分元素集合A`end为[a0,a1,...an/2-1]，而A`即为[reverse(A`start),reverse(A`end)]

由此，通用数组的反转问题可以转化为一个递归问题，其步骤为

2.1 将数组分拆为前后两部分，对其进行反转以后再做拼接;

2.2 当数组剩下的元素为2个或者3个时，交换第一个和最后一个元素;

3 结论

JDK中Integer.reverse的算法思路与上面的分析比较相似，首先以一位为单位两两交换，然后以两位为单元两两交换直至以16位为单元两两交换，最终效果等价于上述算法分析2的非递归操作，栈顶操作为算法分析中的2.2环节，然后依次出栈直至栈底即32位的折半以16位为单元两两交换。