Java 8中Integer.numberOfTrailingZero(int i)实现原理及最终行疑问

先给你吃个定心丸：前面的16/8/4/2位移位确实是在做二分法缩小尾随零的范围，但最后一行绝对不是多余的——它是用来处理前面步骤没覆盖到的最后1位的不确定性，直接决定结果的正确性。

先回顾前面的核心逻辑 #

这个方法的思路是用二分法快速定位第一个非零位的位置，从而算出尾随零的数量：

• 初始n=31（因为int最多有31个尾随零，除了0的情况）
• 每次左移16/8/4/2位，如果移位后结果非零，说明原数的高位区域有非零位，那尾随零的数量肯定小于当前的移位位数，所以把n减去该位数，同时把i更新为移位后的值（聚焦到高位区域继续判断）
• 反之如果移位后结果为零，说明原数的低位区域全是零，尾随零数量大于等于该移位位数，保持n不变，继续用原i判断更小的范围

但问题来了：前面的最小移位是2位，处理完之后，我们还剩下1位的模糊性需要确认——这就是最后一行的作用。

拆解最后一行：n - ((i << 1) >>> 31) #

先看这部分运算的细节：

1. i << 1：把经过前面四次移位后的i左移1位。此时的i已经是经过多次左移后的结果，它的二进制里只有最高位是1，其余都是0（因为每次移位后只保留高位非零的部分）
2. >>> 31：无符号右移31位。因为int是32位，这一步会把左移后的结果的最高位（也就是原来的次高位）移到最低位，得到的结果只能是0或1

这个0或1到底代表什么？我们用三个典型例子来验证：

例子1：i=6（二进制110，尾随零=1）

前面的步骤处理后：

• n最终变为1，i变为0x80000000（二进制最高位是1，其余为0）
• 执行i <<1：左移1位后溢出，结果为0
• 0 >>>31得到0
• 最终结果：1 - 0 =1，完全正确

例子2：i=5（二进制101，尾随零=0）

前面的步骤处理后：

• n最终变为1，i变为0x40000000（二进制第30位是1）
• 执行i <<1：左移1位后得到0x80000000（int的最小值，最高位为1）
• 0x80000000 >>>31得到1
• 最终结果：1 -1 =0，完全正确

例子3：i=4（二进制100，尾随零=2）

前面的步骤处理后：

• y=i<<2结果为0，所以n保持3，i还是0x40000000
• 执行i <<1得到0x80000000，>>>31得1
• 最终结果：3-1=2，正确

总结最后一行的作用 #

经过前面的四次移位后，n是一个近似值，可能比实际尾随零多1，也可能正好等于实际值：

• 如果(i<<1)>>>31得到1：说明当前i的最高位不是int的第31位，左移后还有有效位，意味着前面的n多算了1，需要减1
• 如果得到0：说明当前i的最高位是第31位，左移后溢出为0，意味着n正好是正确的尾随零数量

这一步完美补上了二分法最后1位的判断空白，确保结果精确无误。

内容的提问来源于stack exchange，提问作者S. Nabil