如何使用位运算符找到n位整数的以2为底的对数向下取整？

Question

如何使用位运算符找到n位整数的以2为底的对数向下取整？

algorithmsequencebitwise-operatorsbit-shift

3

我有一个程序，需要经常计算一个整数的以2为底的对数的下取整。因此，在我选择的编程语言中（在C++ 中来自 <cmath> 的代码 floor(std::log2([INT]))）标准库的log2方法的性能无法满足要求，我希望实现最快版本的此算法。我在网上找到了针对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
}

（以上代码摘自这个链接；该代码的注释引用了这个页面，该页面简要介绍了算法的工作原理。）

我需要为256位整数实现此算法的版本。对于n位整数的一般形式非常容易理解：（1）使用具有n个条目的Debruijn序列创建整数数组;（2）对问题中的整数执行原地按位或操作，右移2^i个单位，其中i=1...(n/2);以及（3）返回Debruijn数组的某些条目，其索引等于整数乘以另一个常量向右移动的结果。

第三步是我困惑的地方。如何准确地推导出32位和64位的乘法常数0x07C4ACDDU和0x03f6eaf2cd271461LU？如何推导出应向右移动何值的常数58和27？特别是对于256位整数，这些值将是什么？

提前感谢您的回答。如果这很明显，请原谅我，我在数学方面不太有经验。

- Charles Buchanan

1

我相信你提出的方法可以解决这个问题，但你是否愿意考虑其他解决方案呢？例如，将256位整数分成64个部分，找到最高的非零块，然后使用std::countl_zero。 - harold

@harold std::countl_zero并不是很理想，因为它似乎无法与问题中的类型（boost::multiprecision::uint256_t）配合使用，并且我在boost::multiprecision库中找不到任何重载/替代方法。您知道在这种情况下可以使用哪些替代方法吗？ - Charles Buchanan

当然，这并不像仅仅调用该函数那样方便，但我并没有建议那样做，我的意思是您将搜索数字中最重要的非零块，然后通过在该块上调用countl_zero（而不是整个256位）来快速定位该单个块内的最高有效位。 - harold

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

我同意哈罗德的观点，std::countl_zero() 是最好的选择。自从这个比特操作技巧被设计出来以来，相对于计算机而言，内存速度变得更慢了许多，而处理器通常都有内置指令。

然而，为了回答你的问题，这个技巧结合了几种基本操作。（当我谈论比特索引时，我从最高有效位开始计数。）

以v |= v >> 1;开头的代码行序列通过将至少一个位设置为右侧的每个位来实现其所述目标，即将数字舍入到最接近的2的幂减一（即二进制表示与0*1*匹配的数字）。
- 这些代码行都没有清除v中的位。
- 由于只有右移操作，这些代码行设置的每个位都位于至少一个已设置位的右侧。
- 假设在位置i上有一个已设置位，则我们可以观察到代码行匹配delta的二进制表示形式，例如delta = 13（二进制中的1101）由v |= v >> 1; v |= v >> 4; v |= v >> 8;处理。
使用(n << L) >> (WIDTH - delta)可以从无符号整数n中提取位[L，L+delta)，其中WIDTH是位数。左移截断应该丢弃的高位，而C ++中的右移对于无符号整数是逻辑右移，截断低位并用零填充截断的高位。
假设答案为k，我们想从魔术常数n的索引k开始提取5个（对于32位）或6个（对于64位）位。我们不能通过k进行移位，因为我们仅知道pow2(k)（有点是，我会在下一秒解释），但我们可以使用乘以pow2(k)和左移k之间的等价关系作为解决方法。
实际上，我们只知道pow2(k+1)-1。我们会贪心并节省我们需要获取pow2(k)的两个操作。通过在初始零之后放置5个或6个“1”，我们强制将减一始终导致答案比应该少一（mod 32或64）。
所以de Bruijn序列：这个想法是我们可以通过阅读接下来的5个或6个位来唯一地识别序列中的索引。不幸的是，我们不能让这些位等于索引本身，这就是查找表的用处。

例如，我将此算法改编为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

16进制常量为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，找到一个以0000000011111111开头的256位de Bruijn序列，将其编码为十六进制常量，并构造相应的查找表以配对。

但是，不要这样做。如果您执意不使用库函数，您仍然可能在64位机器上运行，因此您应该测试从大到小的四个字中是否每个字都非零，如果是，则应用64位代码并添加适当的偏移量。