大于 lg N 的最小整数

Question

我在某处读到：

大于lg N 的最小整数 是所需的位数 用二进制表示N，同理 大于的最小整数 log10 N 是位数 要求用十进制表示 N。

Java 语句

for (lgN = 0; N > 0; lgN++, N /= 2) ; 

是一种简单的计算方法 大于 lg N 的最小整数

我可能在这里遗漏了一些东西，但是 Java 语句如何计算大于 lg N 的最小整数？

Answer 1

如果重写为 while 循环可能会更清楚：

lgN = 0
while( N > 0 ) {
    lgN++;
    N = N/2;
}

这可以被认为是“在移走所有 1 之前我们必须右移多少次”（留下零）

Answer 2

把它写在纸上。例如，N = 1750

   lgN   N      N > 0?
1   0    1750   y
2   1    875    y
3   2    437    y
4   3    218    y
5   4    109    y
6   5    54     y
7   6    27     y
8   7    13     y
9   8    6      y  
10  9    3      y
11  10   1      y
12  11   0      n  stop; lgN = 11

Answer 3

这是您应该问的问题的答案，即如何最好地计算它：

不要用循环来执行此操作。直接计算：

int bits = (int) Math.floor(Math.log(n)/Math.log(2)) + 1;

注意不要让n == 0。

Answer 4

仅在示例输入上追踪此内容有任何问题吗？

step 1) N = 10, lgN = 0
step 2) N = 5,  lgN = 1
step 3) N = 2,  lgN = 2
step 4) N = 1,  lgN = 3
step 5) N = 0,  lgN = 4

lgN最后是4。这是大于 log(2, 10) 的最小整数

Answer 5

看起来这是在计算 N 的 log_2。那么用二进制来思考，需要多少位来表示 N？找出答案的方法是计算 N 除以 2 的次数（将 N 中的位向右移 1 个空间）。在 N 达到 0 之前执行此操作的次数就是您正在计算的值。

Answer 6

对于那些偏离正题并试图通过为未提出的问题提供更有效的解决方案来“停止循环疯狂”的人，我建议这同时更高效和可读：

 public int bitsNeeded(int n) {
     return 32 - Integer.numberOfLeadingZeros(n);
 }

作为 Javadoc Integer.numberOfLeadingZeros()< /code>说：

请注意，此方法与以 2 为底的对数密切相关。对于所有正 int 值 x：

• floor(log2(x)) = 31 - numberOfLeadingZeros(x)
• ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)

我之前没有发布此内容，因为正如我所说，它是切线的。 OP 试图理解循环，而不是找到做某事的“最佳”方式。

Answer 7

考虑二进制形式的 N，左侧没有所有零。

例如，对于 19，则为 10011。

每个 N/=2 向右移动一位：

• 10011
• 1001
• 100
• 10
• 1
• 0

当 N 等于 0 时，lgN（步数）等于 log （N）。

Answer 8

lg N 小于 k：

• 当且仅当 N 小于 2^k
• 当且仅当将 N 除以 2, k 次时，结果为 0（请记住，整数除法向下舍入）。

因此，大于 lg N 的最小整数是除以 2 所需的次数才能达到 0，这就是循环的作用。

Answer 9

假设其他一切都正确，代码将使用循环外部存在的“lgN”变量。当循环结束时，“lgN”将是答案。

Answer 10

是的，对于以 2 为底的对数... (ln N)/(ln 2)，不是自然对数

Answer 11

这是一个for循环。其初始条件是 lgN 的值为零。只要 N 大于零，循环就会继续。在循环中的每次迭代中，它都会将 lgN 加 1 并将 N 除以 2。

这是循环所做的非常字面的翻译。它是如何运作的？好吧，第一次循环时，它会增加 lgN 并将 N 除以 2。因此，如果 N 是 1，那么 N 现在为零，我们就完成了。如果 N 大于 1，我们必须再次迭代。每当你能将 N 除以 2 而不会为零时，二进制表示中就需要另一个位。代码基本上会问：“在达到 0 之前，我可以将 N 除以 2 多少次？”这是大于 lg N 的最小整数。