Bit Twiddling Hacks

Java的Integer类有个highestOneBit方法，可以返回一个整数的二进制表示的最左边的1的位置。

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

那么上面的实现到底是在干什么？！😨

Integer类的Javadoc上说highestOneBit的实现参考自书籍Hacker’s Delight。

Implementation note: The implementations of the “bit twiddling” methods (such as highestOneBit and numberOfTrailingZeros) are based on material from Henry S. Warren, Jr.’s Hacker’s Delight, (Addison Wesley, 2002).

或许面试前可以看看这边书，让面试官惊讶一下。

另外，google一下“Bit Twiddling Hacks”，也可以发现很多参考资料。比如这篇pdf，以及这个网站。

Java支持的位操作运算有：~，&，^，|，<<，>>，>>>。

The unsigned right shift operator “»>” shifts a zero into the leftmost position, while the leftmost position after “»” depends on sign extension.

>>>会在最左边补0；>>运算后，最左边是0还是1取决于整数的正负号。