algorithm - 找到一个数在达到 1 之前可以被 2 除多少次的最有效算法 [注 : if possible in O(1) time]

Question

我试过使用日志，但它比迭代版本要花费更多的时间来寻找答案。数字是整数。

Using log:-
int ans = (log(x)/log(2));

Iterative version:-
int temp;
while(x)
{
    temp = temp/2;
    count++;
}
count--;

Answer 1

1. 基本整数数据类型

   对于 x86 架构上的整数，有一个单一的 O(1) 指令:

   • BSR bit scan reverse
     
     

   返回 MSB 设置位的位置。因此，您不需要进行迭代 O(log(n)) 除法、移位或 bin 搜索。为确保符号(2 的补码)不会将负数搞乱，请为此使用 abs 值。

2. 双数

   对于这些，您需要检查 MSW 非零字。并在上面使用#1。这是 O(log(n))。其中 n 是您要测试的数字。

3. float

   这些通常非常简单 O(1)，因为您只需提取指数即可直接告诉您 MSB 设置位的位置。

   此外，log2 由 FPU HW 直接实现，用于大多数架构上的基本 float 数据类型，但它们不会返回整数样式结果 ...