计算小于 N 的基数 2 对数的最大整数

Question

我一直在阅读算法，第 4 版，它定义了一个问题如下：

编写一个静态方法lg()，该方法将一个int值N作为参数并返回int不大于NJava 中的以2 为底的对数的最大值。不要使用数学。

我发现了以下解决方案：

public static int lg(int N) {
    int x = 0;
    for (int n = N; n > 1; n/= 2) x++;
    return x;
}

我想知道为什么该解决方案有效。为什么连续除以 2 可以让我们找到小于参数以 2 为底的对数的最大整数？我确实了解 Java，只是不了解这个特定算法的工作原理。

谢谢你。

Answer 1

这与指数和对数的属性有关。您需要的主要观察是

2lg ⁿ = n，

因为对数是指数的倒数。重新排列该表达式给出

1 = n / 2 ^{lg n}。

换句话说，lg n 的值是您必须将 n 除以 2 才能将其降至 1 的次数。顺便说一下，在研究算法时，这是一个非常好的直觉，因为对数项显示在这样的情况下一直处于上升状态。

关于整数除法的工作原理还有一些其他细微差别，但这是该代码工作背后的基本思想。