java - Integer.numberOfTrailingZero(int i) 如何工作？

Question

这个问题是相关的to但在理解代码的实际工作方式上是不同的。更准确地说，我不明白 numberOfTrailingZeros(int i) 在 java 8 here 中的表现如何计算最终结果。代码如下

   public static int numberOfTrailingZeros(int i) {
    // HD, Figure 5-14
    int y;
    if (i == 0) return 32;
    int n = 31;
    y = i <<16; if (y != 0) { n = n -16; i = y; }
    y = i << 8; if (y != 0) { n = n - 8; i = y; }
    y = i << 4; if (y != 0) { n = n - 4; i = y; }
    y = i << 2; if (y != 0) { n = n - 2; i = y; }
    return n - ((i << 1) >>> 31);
    }

现在我明白了从 16 到 2 的移位操作的目的，但是 n 不会在最后一次移位操作时已经有尾随零的数量:

y = i << 2; if (y != 0) { n = n - 2; i = y; }. 

那是我不明白这一行的目的

n - ((i << 1) >>> 31); 

为什么当 n 已经有正确的值时我们还需要它？

任何人都可以详细说明发生了什么吗？

谢谢!

Answer 1

我将尝试解释该算法。它有点优化，但我将从(希望)更简化的方法开始。

用于判断一个32位数字的尾随零位的个数，即右边有多少个零(假设最高位在左边)。主要思想是将字段分成两半:如果右半部分全为零，我们将右半部分的位数添加到结果中并继续检查左半部分(再次将其除以)；如果右边的不全为零，我们可以忽略左边的，继续检查右边的(结果什么都不加)。

示例:0000 0000 0000 0010 0000 0000 0000 0000 ( 0x0002 0000 )

第一步(不是java代码，所有数字都以2为底，结果是十进制):

i = 0000 0000 0000 0010   0000 0000 0000 0000
left  = 0000 0000 0000 0010
right = 0000 0000 0000 0000
result = 0

由于右边为零，我们将结果加 16(右边部分的实际位数)并继续检查左边部分

第二步:

i = 0000 0000 0000 0010   // left from previous
left =  0000 0000
right = 0000 0010
result = 16

现在右边不为零，所以我们不向结果添加任何内容并继续右边的部分

第三步:

i = 0000 0010    // right from previous
left =  0000
right = 0010
result = 16

右边不为零，没有添加任何结果，继续右边的部分

第四步:

i = 0010    // right from previous
left =  00
right = 10
result = 16

第五步:

i = 10     // right from previous
left = 1
right = 0
result = 16

现在右边是零，所以我们加 1(右边部分的位数)并且没有其他东西可以除(即原始代码的 return 行)

result = 17

优化:该算法不再有左右部分，而是只检查数字的最左边 x 位，如果右边不为零，则将右边部分移到左边，例如第一步:

y = i << 16; if (y != 0) { ... i = y;}

并且，为了避免出现 else部分(我认为)，它以 31 开始结果(所有部分长度的总和 1+2+4+8+16 )，如果右侧(在移动现在左边的部分之后)不为零，则减去位数。再次为第一步:

y = i << 16; if (y != 0) { n = n - 16; ....} 

第二次优化，最后一步，代替

y = i << 1; if (y != 0) { n = n - 1; /* i = y not needed since we are done*/ }
return n;

它只是

return n - ((i << 1) >>> 31);  

在这里((i << 1) >>>31)正在移动 i 的第二位(最左第二位，第二高位)到最左边的位置(消除第一位)，然后将其移到最右边的位置，也就是说，如果第二位为零，则结果为 0，否则为 1。然后从结果中减去它(从头开始撤消总和 31)。

第一个(最左边的)位不需要直接检查。仅当所有其他位都为零时才重要，即数字为 0 , 在最开始检查 ( if (i == 0) return 32; ) 或者是 -1在这种情况下，初始值为 result返回:31 .