计算整数 x 底数 2 的对数近似于小于或等于它的最大整数的最佳方法是什么？
What is the best approach for computing logarithm of an integer x base 2 approximated to the greatest integer less than or equal to it?
在找到基数 2 的 floor(log(x)) 的算法中，计算 floor(log(x)) 的最佳摊销时间复杂度是多少？
计算对数有许多不同的算法，每种算法代表某种不同的权衡。此答案调查了各种方法和所涉及的一些权衡。
方法一：迭代乘法
计算 ⌊logb n⌋ 的一种简单方法是计算序列 b0, b1 , b2, 等等，直到找到一个大于n的值。到那时，我们可以停止，return 指数就在这之前。代码非常简单：
x = 0; # Exponent
bX = 1; # b^Exponent
while (bx <= n) {
x++;
bX *= b;
}
return x - 1;
这有多快？请注意，内部循环递增 x = 0、x = 1、x = 2 等，直到最终我们达到 x = ⌊logb x⌋，每次迭代执行一次乘法。如果我们假设我们正在处理的所有整数都适合单独的机器字——比如说，我们正在使用 int 或 long 或类似的东西——那么每次乘法都需要时间 O(1) 和总体 运行 时间为 O(logb n)，内存使用为 O(1).
方法 2：重复平方
有一个旧的面试问题是这样的。我有一个数字 n，我不会告诉你它是什么。您可以进行 "is x equal to n, less than n, or greater than n?," 形式的查询，您的目标是使用最少的查询来计算出 n 是多少。假设您完全不知道 n 是什么，一种合理的方法是这样工作的：猜测值 1、2、4、8、16、32，...，2k， ...，直到超过 n。那时，对您刚刚找到的范围使用二进制搜索来发现 n 是多少。这 运行s 在时间 O(log n) 中，因为在计算 21 + log2 n = 2n 之后你会超调n，然后在大小为 n 的范围内进行二进制搜索，总共 运行 时间为 O(log n)。
求对数，在某种意义上，有点符合这个问题。我们有一个数字 n 写成 bx 表示一些未知的 x，我们想找到 x。使用上述策略作为起点，我们因此可以计算 b20, b21 , b22, 等等，直到超过 bx.从那里，我们可以 运行 二次二进制搜索来找出所需的确切指数。
我们可以计算值序列 b2k 通过使用
b2k+1 = b2 · 2k = (b2k)2
并找到一个过冲的值如下：
x = 1; # exponent
bX = b; # b^x
while (bX <= n) {
bX *= bX; # bX = bX^2
x *= 2;
}
# Overshot, now do the binary search
问题是如何进行二进制搜索来解决问题。具体来说，我们知道 b2x 太大了，但不知道有多大。与 "guess the number" 游戏不同，二进制搜索 指数 有点棘手。
一个可爱的解决方案是基于这样的想法，即如果 x 是我们正在寻找的值，那么我们可以将 x 写成二进制的一系列位。例如，我们写 x = am-12m-1 + am-2 2m-2 + ... + a121 + a 020。然后
bx = bam-12m-1 + am-22m-2 + ... + a121 + a020
= 2am-12m-1 · 2am-22m-2 · ... · 2a0 20
换句话说，我们可以尝试通过一次一位地构建 x 来发现 bx 是什么。为此，当我们计算值 b1、b2、b4、b8等，我们可以把发现的值写下来。然后，一旦我们超调，我们可以尝试将它们相乘，看看应该包括哪些，应该排除哪些。这是它的样子：
x = 1; // Exponent
bX = b; // b^x
powers = [b]; // b^{2^0}
exps = [1]; // 2^0
while (bX <= n) {
bX *= bX; // bX = bX^2
powers += bX; // Append bX
x++;
exps += x;
}
# Overshot, now recover the bits
resultExp = 1
result = 0;
while (x > 0) {
# If including this bit doesn't overshoot, it's part of the
# representation of x.
if (resultExp * powers[x] <= n) {
resultExp *= powers[x];
result += exps[x];
}
x--;
}
return result;
这当然是一种更复杂的方法，但速度更快。由于我们正在寻找的值是 ⌊bx⌋ 并且我们本质上是使用 "guess the number game" 的解来计算 x 是多少，乘法的次数是O(log logb n)，使用 O(log logb n) 的内存来保存中间幂。这比以前的解决方案快得多！
方法 3：Zeckendorf 表示法
对之前的方法稍作修改，保持 O(log logb n) 的 运行 时间，但放弃了辅助 space 用法到 O(1)。这个想法是，我们不是使用常规系统以二进制形式写指数，而是使用 C++ 中的 Zeckendorf's theorem, which is a binary number system based on the Fibonacci sequence. The advantage is that instead of having to store the intermediate powers of two, we can use the fact that any two consecutive Fibonacci numbers are sufficient to let you compute the next or previous Fibonacci number, allowing us to regenerate the powers of b as needed. Here's an implementation of that idea 写出数字。
方法 4：按位迭代乘法
在某些情况下，您需要求对数底数为二的对数。在这种情况下，您可以利用以下事实：计算机上的数字以二进制表示，并且乘以和除以 2 对应于位移位。
例如，让我们采用之前的迭代乘法方法，我们计算 b 的越来越大的幂，直到超过为止。我们可以使用移位来执行相同的技术，而且速度要快得多：
x = 0; # Exponent
while ((1 << x) <= n) {
x++;
}
return x - 1;
这种方法和以前一样在时间 O(log n) 中仍然是 运行s，但是这种方法可能比乘法更快地实现，因为 CPU 可以更快地进行位移。
方法 5：按位二进制搜索
一个数的以二为底的对数，以二进制表示，等于该数最高位的位置。为了找到那个位，我们可以使用有点像方法 2 的二进制搜索技术，但速度更快，因为机器可以在一条指令中并行处理多个位。基本上，和以前一样，我们生成序列 220, 221，等等，直到我们超过这个数字，给出最高位可以达到多高的上限。从那里，我们进行二进制搜索以找到最高的 1 位。这是它的样子：
x = 1;
while ((1 << x) <= n) {
x *= 2;
}
# We've overshot the high-order bit. Do a binary search to find it.
low = 0;
high = x;
while (low < high) {
mid = (low + high) / 2;
# Form a bitmask with 1s up to and including bit number mid.
# This can be done by computing 2^{m+1} - 1.
mask = (1 << (mid + 1)) - 1
# If the mask overlaps, branch higher
if (mask & n) {
low = mid + 1
}
# Otherwise, branch lower
else {
high = mid
}
}
return high - 1
这种方法 运行s 的时间为 O(log log n)，因为二分查找所花费的时间与要搜索的数量成对数关系，而我们要搜索的数量是 O(log n)。它使用 O(1) 辅助 space.
方法 6：神奇的词级并行
方法 5 中的加速主要是因为我们可以使用单个按位运算并行测试多个位。通过只使用基本的算术运算和位移来做一些 truly amazing things with machine words, it's possible to harness this parallelism to find the most-significant bit in a number in time O(1)，并且 运行 时间完全独立于机器字的大小（例如，算法同样快速地工作）在 16 位、32 位和 64 位机器上）。所涉及的技术相当复杂，我承认直到最近我在教授高级数据结构课程时学习该技术时才知道这是可能的。
总结
总而言之，这里列出了方法、时间复杂度和 space 复杂度。
Approach Which Bases? Time Complexity Space Complexity
--------------------------------------------------------------------------
Iter. Multiplication Any O(log_b n) O(1)
Repeated Squaring Any O(log log_b n) O(log log_b n)
Zeckendorf Logarithm Any O(log log_b n) O(1)
Bitwise Multiplication 2 O(log n) O(1)
Bitwise Binary Search 2 O(log log n) O(1)
Word-Level Parallelism 2 O(1) O(1)
还有很多我在这里没有提到的其他值得探索的算法。一些算法的工作原理是将机器字分成一些固定大小的块，预先计算每个块中第一个 1 位的位置，然后一次测试一个块。这些方法有 运行 次取决于机器字的大小，并且（据我所知）其中 none 比我在此处概述的方法渐进地快。其他方法的工作原理是利用某些处理器的指令立即输出数字中最高有效位的位置，或者使用浮点硬件来工作。那些也很有趣，很精彩，一定要看看！
另一个值得探索的领域是当你有任意精度的整数时。在那里，乘法、除法、移位等的成本是notO(1)，并且这些算法的相对成本发生变化。如果您好奇的话，这绝对值得更深入地探索！
此处包含的代码是用伪代码编写的，因为它主要是为说明而设计的。在实际实现中，您需要担心溢出，处理输入为负或零的情况等。仅供参考。 :-)
希望对您有所帮助！
在找到基数 2 的 floor(log(x)) 的算法中，计算 floor(log(x)) 的最佳摊销时间复杂度是多少？
计算对数有许多不同的算法，每种算法代表某种不同的权衡。此答案调查了各种方法和所涉及的一些权衡。
方法一：迭代乘法
计算 ⌊logb n⌋ 的一种简单方法是计算序列 b0, b1 , b2, 等等，直到找到一个大于n的值。到那时，我们可以停止，return 指数就在这之前。代码非常简单：
x = 0; # Exponent
bX = 1; # b^Exponent
while (bx <= n) {
x++;
bX *= b;
}
return x - 1;
这有多快？请注意，内部循环递增 x = 0、x = 1、x = 2 等，直到最终我们达到 x = ⌊logb x⌋，每次迭代执行一次乘法。如果我们假设我们正在处理的所有整数都适合单独的机器字——比如说，我们正在使用 int 或 long 或类似的东西——那么每次乘法都需要时间 O(1) 和总体 运行 时间为 O(logb n)，内存使用为 O(1).
方法 2：重复平方
有一个旧的面试问题是这样的。我有一个数字 n，我不会告诉你它是什么。您可以进行 "is x equal to n, less than n, or greater than n?," 形式的查询，您的目标是使用最少的查询来计算出 n 是多少。假设您完全不知道 n 是什么，一种合理的方法是这样工作的：猜测值 1、2、4、8、16、32，...，2k， ...，直到超过 n。那时，对您刚刚找到的范围使用二进制搜索来发现 n 是多少。这 运行s 在时间 O(log n) 中，因为在计算 21 + log2 n = 2n 之后你会超调n，然后在大小为 n 的范围内进行二进制搜索，总共 运行 时间为 O(log n)。
求对数，在某种意义上，有点符合这个问题。我们有一个数字 n 写成 bx 表示一些未知的 x，我们想找到 x。使用上述策略作为起点，我们因此可以计算 b20, b21 , b22, 等等，直到超过 bx.从那里，我们可以 运行 二次二进制搜索来找出所需的确切指数。
我们可以计算值序列 b2k 通过使用
b2k+1 = b2 · 2k = (b2k)2
并找到一个过冲的值如下：
x = 1; # exponent
bX = b; # b^x
while (bX <= n) {
bX *= bX; # bX = bX^2
x *= 2;
}
# Overshot, now do the binary search
问题是如何进行二进制搜索来解决问题。具体来说，我们知道 b2x 太大了，但不知道有多大。与 "guess the number" 游戏不同，二进制搜索 指数 有点棘手。
一个可爱的解决方案是基于这样的想法，即如果 x 是我们正在寻找的值，那么我们可以将 x 写成二进制的一系列位。例如，我们写 x = am-12m-1 + am-2 2m-2 + ... + a121 + a 020。然后
bx = bam-12m-1 + am-22m-2 + ... + a121 + a020
= 2am-12m-1 · 2am-22m-2 · ... · 2a0 20
换句话说，我们可以尝试通过一次一位地构建 x 来发现 bx 是什么。为此，当我们计算值 b1、b2、b4、b8等，我们可以把发现的值写下来。然后，一旦我们超调，我们可以尝试将它们相乘，看看应该包括哪些，应该排除哪些。这是它的样子：
x = 1; // Exponent
bX = b; // b^x
powers = [b]; // b^{2^0}
exps = [1]; // 2^0
while (bX <= n) {
bX *= bX; // bX = bX^2
powers += bX; // Append bX
x++;
exps += x;
}
# Overshot, now recover the bits
resultExp = 1
result = 0;
while (x > 0) {
# If including this bit doesn't overshoot, it's part of the
# representation of x.
if (resultExp * powers[x] <= n) {
resultExp *= powers[x];
result += exps[x];
}
x--;
}
return result;
这当然是一种更复杂的方法，但速度更快。由于我们正在寻找的值是 ⌊bx⌋ 并且我们本质上是使用 "guess the number game" 的解来计算 x 是多少，乘法的次数是O(log logb n)，使用 O(log logb n) 的内存来保存中间幂。这比以前的解决方案快得多！
方法 3：Zeckendorf 表示法
对之前的方法稍作修改，保持 O(log logb n) 的 运行 时间，但放弃了辅助 space 用法到 O(1)。这个想法是，我们不是使用常规系统以二进制形式写指数，而是使用 C++ 中的 Zeckendorf's theorem, which is a binary number system based on the Fibonacci sequence. The advantage is that instead of having to store the intermediate powers of two, we can use the fact that any two consecutive Fibonacci numbers are sufficient to let you compute the next or previous Fibonacci number, allowing us to regenerate the powers of b as needed. Here's an implementation of that idea 写出数字。
方法 4：按位迭代乘法
在某些情况下，您需要求对数底数为二的对数。在这种情况下，您可以利用以下事实：计算机上的数字以二进制表示，并且乘以和除以 2 对应于位移位。
例如，让我们采用之前的迭代乘法方法，我们计算 b 的越来越大的幂，直到超过为止。我们可以使用移位来执行相同的技术，而且速度要快得多：
x = 0; # Exponent
while ((1 << x) <= n) {
x++;
}
return x - 1;
这种方法和以前一样在时间 O(log n) 中仍然是 运行s，但是这种方法可能比乘法更快地实现，因为 CPU 可以更快地进行位移。
方法 5：按位二进制搜索
一个数的以二为底的对数，以二进制表示，等于该数最高位的位置。为了找到那个位，我们可以使用有点像方法 2 的二进制搜索技术，但速度更快，因为机器可以在一条指令中并行处理多个位。基本上，和以前一样，我们生成序列 220, 221，等等，直到我们超过这个数字，给出最高位可以达到多高的上限。从那里，我们进行二进制搜索以找到最高的 1 位。这是它的样子：
x = 1;
while ((1 << x) <= n) {
x *= 2;
}
# We've overshot the high-order bit. Do a binary search to find it.
low = 0;
high = x;
while (low < high) {
mid = (low + high) / 2;
# Form a bitmask with 1s up to and including bit number mid.
# This can be done by computing 2^{m+1} - 1.
mask = (1 << (mid + 1)) - 1
# If the mask overlaps, branch higher
if (mask & n) {
low = mid + 1
}
# Otherwise, branch lower
else {
high = mid
}
}
return high - 1
这种方法 运行s 的时间为 O(log log n)，因为二分查找所花费的时间与要搜索的数量成对数关系，而我们要搜索的数量是 O(log n)。它使用 O(1) 辅助 space.
方法 6：神奇的词级并行
方法 5 中的加速主要是因为我们可以使用单个按位运算并行测试多个位。通过只使用基本的算术运算和位移来做一些 truly amazing things with machine words, it's possible to harness this parallelism to find the most-significant bit in a number in time O(1)，并且 运行 时间完全独立于机器字的大小（例如，算法同样快速地工作）在 16 位、32 位和 64 位机器上）。所涉及的技术相当复杂，我承认直到最近我在教授高级数据结构课程时学习该技术时才知道这是可能的。
总结
总而言之，这里列出了方法、时间复杂度和 space 复杂度。
Approach Which Bases? Time Complexity Space Complexity
--------------------------------------------------------------------------
Iter. Multiplication Any O(log_b n) O(1)
Repeated Squaring Any O(log log_b n) O(log log_b n)
Zeckendorf Logarithm Any O(log log_b n) O(1)
Bitwise Multiplication 2 O(log n) O(1)
Bitwise Binary Search 2 O(log log n) O(1)
Word-Level Parallelism 2 O(1) O(1)
还有很多我在这里没有提到的其他值得探索的算法。一些算法的工作原理是将机器字分成一些固定大小的块，预先计算每个块中第一个 1 位的位置，然后一次测试一个块。这些方法有 运行 次取决于机器字的大小，并且（据我所知）其中 none 比我在此处概述的方法渐进地快。其他方法的工作原理是利用某些处理器的指令立即输出数字中最高有效位的位置，或者使用浮点硬件来工作。那些也很有趣，很精彩，一定要看看！
另一个值得探索的领域是当你有任意精度的整数时。在那里，乘法、除法、移位等的成本是notO(1)，并且这些算法的相对成本发生变化。如果您好奇的话，这绝对值得更深入地探索！
此处包含的代码是用伪代码编写的，因为它主要是为说明而设计的。在实际实现中，您需要担心溢出，处理输入为负或零的情况等。仅供参考。 :-)
希望对您有所帮助！