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

我有一个程序，其中需要非常频繁地计算整数的对数基-2的底。因此，标准库的log2方法在我选择的语言(C++中<cmath>中的floor(std::log2([INT])))中的性能不令人满意，我希望实现该算法的最快版本。我在网上找到了使用逐位运算符来计算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)从Debruijn序列中创建一个包含n个条目的整数数组；(2) 在i=1…(n/2)的情况下，按位执行或对右移2^i的整数执行；以及(3)返回一些Debruijn数组的条目，其索引等于整数乘以右移了另一个常数的常数。

第三步是我感到困惑的地方。如何分别推导出0x07C4ACDDU和0x03f6eaf2cd271461LU作为32位和64位的乘法常数？如何导出58和27作为应该右移的常数？对于一个256位的整数，这些值会是什么？

提前谢谢。很抱歉，如果这很明显的话，我没有受过很好的数学教育。

我同意harold的观点，std::countl_zero()是我们要走的路。记忆力自从这件事以来，相对于计算速度慢了很多hack是经过设计的，处理器通常都有内置指令。

然而，为了回答你的问题，这个黑客组合了几个基元。(当我谈到位索引时，我是从最多到最低有效，从零开始计数。)

以v |= v >> 1;开头的行序列实现了规定的四舍五入到二减一的最接近幂的目标(即二进制表示与0*1*匹配的数字)将每个比特设置在至少一个设置比特的右边。
- 这些行都不清除v中的位
- 由于只有右移，所以这些线设置的每个位在至少一个设置位的右边
- 给定位置i处的设置位，我们观察到位置i + delta将由线路保证设置匹配delta的二进制表示，例如delta = 13(二进制1101)由处理v |= v >> 1; v |= v >> 4; v |= v >> 8;
从无符号整数CCD_ 17中提取位CCD_CCD_ 18位可以用CCD_。左移位截断应当丢弃的高位，而右移，在C++中是逻辑的，表示无符号，截断并用零填充截断的高位。
假设答案是k，我们想提取5(=log2(32)，对于32位)或以索引k开始的6(＝log2(64)，对于64位)位从魔术常数CCD_ 22。我们不能乘k，因为我们只有知道pow2(k)(有点，我马上就会知道)，但我们可以使用乘以pow2(k)和left之间的等价关系以CCD_ 26作为变通方法。
实际上我们只知道pow2(k+1) - 1。我们会变得贪婪剃掉我们需要的两个手术来获得pow2(k)。通过放置5或6在最初的零之后的一，我们强制该负一总是使答案比应该的少一个(mod 32或64)。
因此，德布鲁因序列：我们可以唯一地识别通过读取接下来的5或6个比特，我们在序列中的索引。我们不是幸运的是能够使这些比特等于索引，这就是查找表的来源。

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

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

德布鲁因序列是00011101，用三位写出分段是

(index−1)mod 8位
7		0		1		2		3		4		5		6

相关内容

最新更新

热门标签：