如何使用按位运算符找到 n 位整数的 log-base-2 的底数？

Question

我有一个程序需要非常频繁地计算整数的 log-base-2 的底数。作为结果，标准库的 log2 方法在我选择的语言中的性能（floor(std::log2([INT])) 来自 <cmath> 在 C++ 中）并不令人满意，我想实现该算法的最快版本。我在网上找到了使用按位运算符计算 32 位和 64 位整数值的版本：

INT Y(log2i)(const INT m)
{
  /* Special case, zero or negative input. */
  if (m <= 0)
    return -1;

#if SIZEOF_PTRDIFF_T == 8
  /* Hash map with return values based on De Bruijn sequence. */
  static INT debruijn[64] =
  {
    0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49,
    18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15,
    8, 23, 7, 6, 5, 63
  };

  register uint64_t v = (uint64_t)(m);

  /* Round down to one less than a power of 2. */
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v |= v >> 32;

  /* 0x03f6eaf2cd271461 is a hexadecimal representation of a De Bruijn
   * sequence for binary words of length 6. The binary representation
   * starts with 000000111111. This is required to make it work with one less
   * than a power of 2 instead of an actual power of 2.
   */
  return debruijn[(uint64_t)(v * 0x03f6eaf2cd271461LU) >> 58];
#elif SIZEOF_PTRDIFF_T == 4
  /* Hash map with return values based on De Bruijn sequence. */
  static INT debruijn[32] =
  {
    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28,
    15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
  };

  register uint32_t v = (uint32_t)(m);

  /* Round down to one less than a power of 2. */
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;

  /* 0x07C4ACDD is a hexadecimal representation of a De Bruijn sequence for
   * binary words of length 5. The binary representation starts with
   * 0000011111. This is required to make it work with one less than a power of
   * 2 instead of an actual power of 2.
   */
  return debruijn[(uint32_t)(v * 0x07C4ACDDU) >> 27];
#else
#error Incompatible size of ptrdiff_t
#endif
}

（以上代码摘自 this link; the comments of said code reference this page，简要概述了算法的工作原理）。

我需要为 256 位整数实现此算法的一个版本。对于 n 位整数，一般形式很容易理解： (1) 从 Debruijn 序列创建一个整数数组，其中包含 n 个条目； (2) 对有问题的整数执行就地按位或右移 2^i for i=1...(n/2)；和 (3) return Debruijn 数组的一些条目，其索引等于整数乘以一个常量右移另一个常量。

第三步是我困惑的地方。究竟如何推导 0x07C4ACDDU 和 0x03f6eaf2cd271461LU 分别作为 32 位和 64 位的乘法常数？如何推导出 58 和 27 作为应该右移的常数？特别是对于 256 位整数，这些值是多少？

提前致谢。很抱歉，如果这很明显，我的数学教育不是很好。

Answer 1

我同意哈罗德的观点，std::countl_zero() 是正确的选择。记忆相对于计算来说已经慢了很多，因为这个 bit-twiddling hack 被设计出来，处理器通常有内置指令。

然而，为了回答您的问题，这个 hack 结合了几个原语。（当我谈论位索引时，我是从大多数到最不重要，从零开始计数。）

以v |= v >> 1;开头的行序列实现了它的四舍五入到最接近的二减一的幂的既定目标（即二进制表示匹配 0*1* 的数字）将每一位设置到至少一个设置位的右边。
- None 这些行清除 v.
- 因为只有右移，这些行设置的每一位位于至少一组位的右侧。
- 给定位置 i 的设置位，我们观察到位在位置 i + delta 将由行保证匹配 delta 的二进制表示，例如 delta = 13 （二进制为 1101）由 v |= v >> 1; v |= v >> 4; v |= v >> 8;.
从无符号整数 n 中提取位 [L, L+delta) WIDTH 位可以用 (n << L) >> (WIDTH - delta) 完成。左移截断应该丢弃的高位，和右移，这在 C++ 中对于无符号是合乎逻辑的，截断低位并用零填充截断的高位。
鉴于答案是k，我们要提取5(=log2(32)，对于 32 位）或 6（= log2(64)，对于 64 位）以索引 k 开头的位来自魔法常数 n。我们不能移动 k 因为我们只知道 pow2(k)（有点，我马上就会讲到），但我们可以使用乘以 pow2(k) 和左乘之间的等价性作为解决方法，移动 k。
其实我们只知道pow2(k+1) - 1。我们会变得贪婪并且剃掉我们需要得到的两个操作 pow2(k)。通过放置 5 或 6 初始零之后的那些，我们总是强制减一导致答案比应有的少一（mod 32 或 64).
所以de Bruijn序列：思路是我们可以唯一识别我们通过读取接下来的 5 或 6 位在序列中的索引。我们不是很幸运能够让这些位等于索引，这就是查找 table 的用武之地。

例如，我会将此算法调整为 8 位字。我们从

开始

v |= v >> 1;
v |= v >> 2;
v |= v >> 4;

de Bruijn序列是00011101，用三位写出来段是

(index − 1) mod 8	bits	value	(value − 1) mod 8
7	000	0	7
0	001	1	0
1	011	3	2
2	111	7	6
3	110	6	5
4	101	5	4
5	010	2	1
6	100	4	3

十六进制常数为0x1D，右移为8 − log2(8) = 5，则 table 是通过反转上面的排列得出的： {0, 5, 1, 6, 4, 3, 2, 7}.

所以，假设，如果我们想让这个算法适应 256 位字长，我们将添加 v |= v >> 64; v |= v >> 128;，将 shift 更改为 256 − log2(256) = 256 − 8 = 248，找到一个 256 位的 de Bruijn 序列以 0000000011111111 开头，将其编码为十六进制常量，然后构造适当的查找 table 以与之配对。

但是喜欢，不要。如果你坚持不使用库函数，你就是仍然可能在 64 位机器上，所以你应该测试每个从大到小的四个词中有一个不为零，如果是，应用 64 位代码并添加适当的偏移量。

如何使用按位运算符找到 n 位整数的 log-base-2 的底数？

How does one find the floor of the log-base-2 of an n-bit integer using bitwise operators?

algorithm

bit-shift

sequence

bitwise-operators