什么是计算 floor(log(m / n)) 的有效方法，其中 m 和 n 是整数？

Question

基本上，正如标题所说。我想知道一种计算方法floor(log2(x / y))，其中x和y是非零无符号机器整数，在尽可能少的周期内（尽可能避免使用分支，内存带宽，除法等在微小部分中很昂贵的东西像这样的代码）。这里需要准确的（整数）答案。我在考虑如何通过有效地计算来优化Adaptive Shivers Sort的外循环，因为它需要计算floor(log2(r / c))，其中r是c算法的运行长度和元参数；假设x <= y适用于此类离线版本的解决方案，其中c 被选择为等于输入的长度，但通用解决方案在其他设置中可能有用。

您可以假设使用PopCountand CountLeadingZeros/CountTrailingZeros、常见的 SSE 样式指令，甚至浮点计算——但它需要是处理器可以在短短几个周期内完成的事情。

Answer 1

像这样的事情怎么样，部分灵感来自 NXTangl 的评论？应用clz到xandy并将它们都移位，使它们的前导位位于最高位位置（31 或 63）。假设k这两个移位量之间的差异。无论是现在k还是k-1是你正在寻找的结果，你能辨别的情况下，通过该移值越大。

Answer 2

嗯，这不是一个正确的答案，但这里有一些有趣的特殊情况。

请记住，对于任何 k，log_k(x/y) = log_k(x) - log_k(y)。现在，

1. 如果 y 是 2 的幂，则下限 (log_2(x/y)) = 下限 (log_2(x) - log_2(y)) = 下限 (log_2(x)) - log_2(y)
2. 如果x是2的幂，则floor(log_2(x/y))=floor(log_2(x)-log_2(y))=log_2(x)+floor(-log_2(y))=log_2(x)- ceil(log_2(y)) =
3. 如果 n 是非负自然数，则 ceil(log_2(n)) = Floor(log_2(2n-1))

因此：

• 如果 x,y 是 2 的幂，则有：
  log_2(x/y) = (size_in_bits - ctz(y)) - (size_in_bits - ctz(x)) = ctz(x) - ctz(y)
• 如果只有 y 是 2 的幂，我们还可以通过参数 (1) 使用 ctz(x) - ctz(y)。
• 如果 x 是 2 的幂，我们可以通过参数 (2)、(3) 使用 ctz(x) - ctz(2*y-1)。

因此，如果您碰巧能够做出这些假设之一 - 或者甚至不是确定地做出这些假设，但具有足够高的概率，那么您将获得相当有效的计算。