algorithm - 如何使用按位运算符找到 n 位整数的对数基数 2 的底？

Question

我有一个程序，需要非常频繁地计算一个整数的 log-base-2 的下限。作为结果，标准库的 log2 方法在我选择的语言(C++ 中的 floor(std::log2([INT])) 来自 <cmath>)中的性能并不令人满意，我想实现该算法的最快版本。我在网上找到了使用按位运算符计算 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 ；所述代码引用的注释 this page ，简要概述了算法的工作原理)。
我需要为 256 位整数实现这个算法的一个版本。 n 位整数的一般形式相当容易理解: (1) 从具有 n 个条目的 Debruijn 序列创建一个整数数组； (2) 对有问题的整数执行就地按位或右移 2^i for i=1...(n/2); (3) 返回 Debruijn 数组的一些条目，其索引等于整数乘以右移另一个常数的常数。
第三步是我困惑的地方。究竟是如何推导的 0x07C4ACDDU和 0x03f6eaf2cd271461LU分别作为 32 位和 64 位的乘法常数？怎么推导 58和 27作为应该右移的常数？特别是对于 256 位整数，这些值是什么？
提前致谢。对不起，如果这很明显，我在数学方面没有受过很好的教育。

Answer 1

我同意哈罗德的观点 std::countl_zero()是要走的路。内存
自从这个比特摆弄以来，相对于计算已经慢了很多
hack 是设计的，并且处理器通常具有内置指令。
然而，为了回答你的问题，这个 hack 结合了几个
原语。 (当我谈到位索引时，我是从大多数到
最不重要，从零开始计数。)

以 v |= v >> 1; 开头的行序列达到其
四舍五入到最接近的二减一的幂的既定目标
(即，二进制表示与 0*1* 匹配的数字)由
将每一位设置在至少一个设置位的右侧。

这些行都没有清除 v 中的位.

由于只有右移，这些行设置的每一位
位于至少一个设置位的右侧。

给定位置 i 的设置位，我们观察到一点在
职位i + delta将保证由行设置
匹配 delta的二进制表示，例如，delta = 13(二进制 1101)由v |= v >> 1; v |= v >> 4; v |= v >> 8; .

提取位 [L, L+delta)来自一个无符号整数 n和WIDTH位可以用 (n << L) >> (WIDTH - delta) 完成.
左移截断应丢弃的高位，
和右移，在 C++ 中对于无符号是合乎逻辑的，截断
低位并用零填充截断的高位。

鉴于答案是 k , 我们要提取 5 (= log2(32), for
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 位，我们在序列中的索引。我们不是
很幸运能够让这些位等于索引，
这就是查找表的用武之地。

作为一个例子，我将这个算法适用于 8 位字。我们从

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

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


(索引 - 1)mod 8
位
值(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，
表格是通过反转上面的排列得出的: {0, 5, 1, 6, 4, 3, 2, 7} .
因此，假设，如果我们想将此算法调整为 256 位
字大小，我们将添加 v |= v >> 64; v |= v >> 128; , 将移位更改为
256 − log2(256) = 256 − 8 = 248，找到一个 256 位的 de Bruijn 序列
以 0000000011111111 开头，将其编码为十六进制常量，并且
构建适当的查找表以与之配对。
但是，不要。如果你坚持不使用库函数，你就是
仍然可能在 64 位机器上，所以你应该测试每个
从大到小的四个词中的一个非零，如果是，则应用
64 位代码并添加适当的偏移量。