我有一个程序,需要经常计算一个整数的以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位整数,这些值将是什么?提前感谢您的回答。如果这很明显,请原谅我,我在数学方面不太有经验。
boost::multiprecision::uint256_t
)配合使用,并且我在boost::multiprecision
库中找不到任何重载/替代方法。您知道在这种情况下可以使用哪些替代方法吗? - Charles Buchanancountl_zero
(而不是整个256位)来快速定位该单个块内的最高有效位。 - harold