如何高效计算 floor(log(m / n))，其中 m 和 n 是整数？

Question

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

您可以假设使用常见的SSE样式指令PopCount和CountLeadingZeros/CountTrailingZeros或浮点运算-- 但它需要是处理器可以在几个周期内完成的东西。

- NXTangl

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Samuel Liew

Answer 1

像这样的思路如何，部分灵感来自于NXTangl的评论？将clz应用到x和y，并将它们两个的位移，使它们的最高有效位在顶部位（31或63）。让k成为这两个位移量之间的差异。现在，k或k-1是您要查找的结果之一，您可以通过哪个移位值较大来区分这些情况。

- R.. GitHub STOP HELPING ICE

---

这基本上就是我想要的，而且它应该可以工作。它基本上将问题简化为 N - M + floor(log2((x << M) / (y << N)))；其中M和N是整数，它简化为 floor(log2(x / y))，如果我们选择具有clz的M和N，使得 1/2 <= (x<<M)/(y<<N) < 2，那么我们可以找到 floor(log2((x << M) / (y << N)) = (x << M) < (y << N) ? 1 : 0。换句话说，N - M - ((x << M) < (y << N))。 - NXTangl

@NXTangl：还要注意的是，< 不一定需要是一个分支；只需进行减法运算（结果比总 int 大小少 1 位），并将最高位向下移动到位置 0，即可得到从 N-M 中减去的值。 - R.. GitHub STOP HELPING ICE

两个数字相除的对数是一个减法，如果你也想去掉它。 - Michael Dorgan

Answer 2

嗯，这不算是一个正式的答案，但下面有一些有趣的特殊情况。

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

1. 如果y是2的幂次，那么floor(log_2(x/y)) = floor(log_2(x) - log_2(y)) = floor(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的幂次方，我们也可以使用ctz(x) - ctz(y)的论证（1）。
• 如果只有x是2的幂次方，我们可以使用ctz(x) - ctz(2*y-1)的论证（2），（3）。

因此，如果您恰好能够做出这些假设 - 或者甚至不确定地做出它们，但概率足够高，您将得到相当有效的计算。

- einpoklum