java - 我不认为Long.java中的numberOfLeadingZeros(long i)是基于floor(log2(x)) = 63 - numberOfLeadingZeros(x)!

Question

这是 Long.java 中的 numberOfLeadingZeros(long i) :

public static int numberOfLeadingZeros(long i) {
        // HD, Figure 5-6
         if (i == 0)
            return 64;
        int n = 1;
        int x = (int)(i >>> 32);
        if (x == 0) { n += 32; x = (int)i; }
        if (x >>> 16 == 0) { n += 16; x <<= 16; }
        if (x >>> 24 == 0) { n +=  8; x <<=  8; }
        if (x >>> 28 == 0) { n +=  4; x <<=  4; }
        if (x >>> 30 == 0) { n +=  2; x <<=  2; }
        n -= x >>> 31;
        return n;
}

作者说它是基于floor(log2(x)) = 63 - numberOfLeadingZeros(x)或ceil(log2(x)) = 64 - numberOfLeadingZeros(x - 1)，是真的吗？还是我太笨了，听不懂？

谁能给我解释一下吗？谢谢!

Answer 1

一个数字的位数是 floor(log(num)) + 1 (log 的基数正确。)如果总数字空间为 x，则前导零的数量为

x - (floor(log(num)) + 1) =
(x - 1) - floor(log(num))

所以在你的例子中，共有 64 位数字和二进制数

leadingZeros(num) = 63 - floor(log_2(num))

编辑:

>>>是 Java 中的无符号右移运算符， <<是左移。 n >>> 32将转移n向右移动 32 位，同时用 0 填充空白。

所以算法的工作原理如下:

0000000000000000000000000000000000000000000001011010100000101011

1. 类次i向右 32 位，所以 x仅包含高 32 位。

   00000000000000000000000000000000

2. 如果 (a) 这是 0，我们知道高 32 位是 0，因此将 32 添加到前导零计数并集中于低 32 位。 (b) 否则，该值不为零，因此该数字的前导零少于 32 个。重点关注高 32 位。

3. 类次x向右移动 16 位。

   0000000000000101

   通过相同的过程: (a) 如果这是 0，则将 16 添加到前导零计数并集中于下一个最低 16 位(通过将它们左移到我们正在工作的区域中。) (b) 如果这是非零的，那么我们需要添加的前导零少于 16 个。

4. 对下一个字节重复此操作，然后是接下来的 4 位、2 位和最后一位。