Java的Integer类方法解读 Java

highestOneBit 获取一个int类型的二进制取整

public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); }

上述代码粗看会不理解实现原理，但是跟着推导一次就能理解算法的思想。假定一个int的二进制表达式是100001000，这个常数的迭代过程如下：

第一次结束 100001000 -> 110001100
第二次结束 110001100 -> 111101111
第三次结束 111101111 -> 111111111
第四次结束 111111111 -> 111111111
第五次结束 111111111 -> 111111111

然后返回值为111111111-11111111 = 100000000。
整个实现过程中，即为不停的将首位1和后续的位进行与操作，并且首位1第一次复制成2个，第二次2*2复制成4个，第三次复制成2*4 = 8个（如果这个int大于2^8)，以此类推，按照指数形式将首位1向后与之后，我们最后就能让所有位全部变成1。最后右移1位然后相减，去掉首位之后的所有的1即可。
【Java的Integer类方法解读】此种实现方式，简化了迭代次数，并且由于充分利用上一次的赋值结果，所以不用考虑第三位是否成功被赋值，第五位成功被赋值等（因为在(int)log2(n)+1)次会被赋值。