Java的Integer类方法解读

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即可。

此种实现方式，简化了迭代次数，并且由于充分利用上一次的赋值结果，所以不用考虑第三位是否成功被赋值，第五位成功被赋值等（因为在(int)log2(n)+1)次会被赋值。

Donate