从JDK源码看二分思想

在查看JDK源码的时候，看到了Integer类中有一个方法numberOfLeadingZeros，这个方法的作用是计算目标值i(十进制)转换二进制(int类型长度为32位)数后左边共有多少位0，这个方法本身对编程来说用的不多，但其思想却值得我们好好学习一下。

其源码如下：

public static int numberOfLeadingZeros(int i) {
        if (i == 0)
            return 32;
        int n = 1;
        if (i >>> 16 == 0) { n += 16; i <<= 16; }
        if (i >>> 24 == 0) { n +=  8; i <<=  8; }
        if (i >>> 28 == 0) { n +=  4; i <<=  4; }
        if (i >>> 30 == 0) { n +=  2; i <<=  2; }
        n -= i >>> 31;
        return n;
}

我们以1314520这个数字来查看二分思想，1314520转换为二进制为 00000000 00010100 00001110 11011000，所为二分就是把整体平均分为两部分。

第一步：

i >>> 16(右移16位)，就只剩下00000000 00010100不为0，既然不为0零那剩下的被移走的那16位，也就是右边16位，就没什么用了，继续分析剩下的16位，即左边的16位。

第二步:

i >>> 24(右移24位)，实际上是将左边的16位二分，来进行分析，剩下00000000为0，这样就有了8位零，计数器n加8，此时n为9，左边8位为零那再分析左边8位就没意义了，目标数右移8位后，刚好将左边没意义的8位移走，继续分析右边8位。

第三步：

i >>> 28(右移28位)，将剩下要分析的8位，也就是00010100二分，得到左边4位0001不为0，则继续分析左边4位

第四步：

i >>> 30(右移301位)，将待分析的4位0001二分，知易行难00为0，计数器n加2，此时n为11，同理，将i左移2位去掉已经分析过的为零的2位，然后再分析剩下的2位

第五步：

n -= i >>> 31，到这个时候只需要分析右边的1位就好了，如果为0则n不变，如果为1则n-1。等等，这里为零为什么不变，为1反而要减1，我们的理解不是应该为0则n+1,为1则n不变吗。原因很简单，那就是n的初始值为1而不是0。这里最后一位为0，故n不变，为11.
最终答案也就是11。

注意：

一、二分之后如果左边不为0则下一个要分析的目标是左边，如果为0则下一个要分析的目标是右边，怎样再下一次移动相同位数的时候，既可以分析左边，又可以分析右边呢，作者的做法就是，如果分析左边，则数字i不变，如果分析右边则将无用的左边移走然后赋值给i，具体的 i >>> 16 后有两种情况。1）左边为0，数字i右移16位，等下次i >>> 24位的时候分析的就是右边16位，2）左边不为0，则分析左边16位，i不变，等下次i >>> 24位的时候分析的就是左边16位。
二、二分后只用判断左边的位数就好，如果左边为0，则右边肯定不为0，因为左右合起来不为0；如果左边不为0，那右边为不为0没意义。

二分思想在编程的世界里用处还是很广泛的，如二分查找，效率还是挺高的。解释的有点详细（你也可以说是啰嗦），但目标只有一个就是让大家理解这个思想。