如何快速找到二进制对数？(O(1)充其量)

Question

有没有非常快的方法来找到整数的二进制对数？例如,给定一个数x = 52656145834278593348959013841835216159447547700274555627155488768这样的算法必须找到定义Y = Log(X,2),它是215 x为总是2的幂.

问题似乎很简单.所需要的只是找到最重要的1位的位置.有一个众所周知的方法FloorLog,但它不是很快,特别是对于很长的多字整数.

什么是最快的方法？

Answer 1

是位摆弄黑客,你在找什么？

Answer 2

快速入侵:大多数浮点数表示自动标准化值,这意味着它们有效地执行了硬件中提到的ChristofferHammarström循环.因此,如果数字在FP表示的指数范围内,那么只需将整数转换为FP并提取指数即可.(在您的情况下,您的整数输入需要多个机器字,因此需要在转换中执行多个"shift".)

Answer 3

如果整数存储在 a 中uint32_t a[]，那么我明显的解决方案如下：

1. 运行线性搜索以查找a[]最高值的非零uint32_t值（如果您的计算机具有本机支持，则测试用于该搜索的值）a[i]a[]uint64_tuint64_t

2. 应用位旋转技巧来查找您在步骤 1 中找到的值b的二进制日志。uint32_ta[i]

3. 评价32*i+b。