计算小于 N 的以 2 为底的对数的最大整数

Question

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

Write a static method lg() that takes an int value N as an argument and returns the largest int not larger than the base-2 logarithm of N in Java. Do not use Math.

我发现了以下解决方案：

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

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

2^{lg n} = n,

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

1 = n / 2^{lg n}.

换句话说，lg n 的值是将 n 除以 2 以使其降为 1 的次数。顺便说一下，这在研究算法时是一个非常好的直觉，因为对数项总是出现在这样的上下文中。

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

Answer 2

根据对数恒等式 log(a/b) = log(a) - log(b)。

您正在搜索最大整数 x 以便：

x <= log2(n)

使用上面的身份并考虑到 log2(2) = 1 我们得到：

x <= log2(n/2) + log2(2)
x <= log2(n/2) + 1
x <= log2(n/4) + 2
x <= log2(n/8) + 3
...
x <= log2(1) + k            
x <= k                   (since log2(1) = 0)

因此 x 是您在达到 1 之前将 n 除以 2 的次数。

Answer 3

答案纯属数学，

log₂(n) = ln(n)/ln(2) = x

通过应用指数规则：

ln(n) = ln(2)*(x)

n = 2^x

因此你必须除以2直到值小于1才能得到最接近它的整数。

Answer 4

我们正在寻找最大的整数 x 使得 x <= log_2(N) 即 2^x <= N

或等效的 2^x <= N < 2^{x+1}

令N_0=N

and for k > 0, N_k N_{k-1} 除以 2 的商和 r_k 在 {0, 1} 中的余数 (N_{k-1 } = 2.N_k + r_k)

我们有：

2^{x-1} <= N_1 + (r_1 / 2) < 2^x

但是 0 <= r_1 / 2 <= 1/2 和其他数字是整数所以等同于

2^{x-1} <= N_1 < 2^x

我们先后有：

2^{x-1} <= N_1 < 2^x

2^{x-2} <= N_2 < 2^{x-1}

…

2^{x-x} <= N_x < 2^{x-x+1}

最后也写成1 <= N_x < 2

但是 N_x 是一个整数所以 N_x = 1

因此x是N大于等于1的除以2的个数

我们可以从 N_0 = N 开始并保持大于 1，而不是从 N_1 开始。

计算小于 N 的以 2 为底的对数的最大整数

Calculating the largest int less than the base 2 log of N

java

algorithm

math

logarithm