计算小于N的最大整数，其对以2为底的对数的结果。

Question

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

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

我找到了以下解决方案：

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

我想知道为什么这个解决方案有效。为什么连续除以2能帮助我们找到小于参数的以2为底的对数的最大整数？我理解Java，但不知道这个特定算法是如何工作的。

谢谢。

- user6233283

---

我投票关闭此问题，因为它是一个关于数学而不是编程的问题。 - Joe C

@JoeC 你认为我应该在数学堆栈交换中询问吗？ - user6233283

我对该网站不够熟悉，无法提供建议，除了指向他们的帮助中心，以便您做出判断。 - Joe C

@JoeC https://meta.stackexchange.com/questions/165519/where-should-i-post-questions-about-algorithms-stack-overflow-or-software-engin - Naman

以2为底数的x的对数等于x可以被2整除多少次，直到达到1（包含1）。 - Soner from The Ottoman Empire

Answer 1

这与指数和对数的属性有关。你需要注意的主要观察是：

2^{lg n} = n，

因为对数是指数的反函数。重排这个表达式得到

1 = n / 2^{lg n}.

换句话说，lg n的值是你需要将n除以2多少次才能将其降至1。顺便提一下，在研究算法时具备这种直觉非常重要，因为在这些上下文中经常出现对数项。

这里还有一些关于整除运算如何工作的细节，但这就是代码有效的基本原理。

- templatetypedef

---

谢谢。您所说的“lg”是指自然对数还是以10为底的对数？ - user6233283

我在计算机科学中看到的惯例是，lg指的是以2为底的对数。你可以通过注意只有以2为底的对数满足上述数学要求来验证这一点。 - templatetypedef

@templatetypedef “ISO 31-11和ISO 80000-2标准建议使用lb n。根据这些标准，不应该使用lg n表示二进制对数，因为它是保留给常用对数log10 n的。" 简而言之，在怀疑时请指定底数。 - Kashyap

我不知道！我看到很多论文中使用了lg约定，通常在不能与其他对数底混淆的情况下使用。 - templatetypedef

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是在除以2达到1之前你将n除以2的次数。

- Georgi Gerganov

Answer 3

答案纯粹是数学相关的， log₂(n) = ln(n)/ln(2) = x

通过指数规则： ln(n) = ln(2)*(x) n = 2^x

因此，你必须一直除以2，直到该值小于1为止，以便获得最接近它的整数。

- Mohammad Kurjieh

Answer 4

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

或等价于 2^x <= N < 2^{x+1}

令N_0=N

对于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除以2后余数大于或等于1的除以2的次数。

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

- Jean-Claude Colette