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

Question

有没有非常快的方法来找到整数的二进制对数？例如，给定数字x = 52656145834278593348959013841835216159447547700274555627155488768这样的算法必须找到y = log（x，2），即215. x总是2的幂。

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

什么是最快的方法？

Answer 1

Bit Twiddling Hacks你在找什么？

Answer 2

快速入侵：大多数浮点数表示自动规范化值，这意味着它们在硬件中有效地执行循环Christoffer Hammarström mentioned。因此，如果数字在FP表示的指数范围内，那么只需将整数转换为FP并提取指数即可。 （在您的情况下，您的整数输入需要多个机器字，因此需要在转换中执行多个“shift”。）

Answer 3

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

1. 在a[]上运行线性搜索，找到uint32_t中最高值的非零a[i]值a[]（如果您的机器具有本机uint64_t支持，则使用uint64_t进行该搜索测试）
2. 应用bit twiddling hacks查找在步骤1中找到的b值uint32_t的二进制日志a[i]。
3. 评估32*i+b。

Answer 4

答案是实现或语言相关。任何实现都可以存储有效位的数量以及数据，因为它通常是有用的。如果必须计算，则找到最重要的单词/肢体和该单词中最重要的位。

Answer 5

通过使用二进制搜索，我头脑中的最佳选择是O（log（logn））方法。以下是64位（<= 2^63 - 1）数字（在C ++中）的示例：

int log2(int64_t num) {
    int res = 0, pw = 0;    
    for(int i = 32; i > 0; i --) {
        res += i;
        if(((1LL << res) - 1) & num)
            res -= i;
    }
    return res;
}

这个算法基本上会为我提供最高数量的res，比如(2^res - 1 & num) == 0。当然，对于任何数字，你可以在类似的事情中解决它：

int log2_better(int64_t num) {
    var res = 0;
    for(i = 32; i > 0; i >>= 1) {
        if( (1LL << (res + i)) <= num )
            res += i;
    }
    return res;
}

注意，该方法依赖于“bitshift”操作或多或少为O（1）的事实。如果不是这种情况，则必须预先计算2的所有幂，或2^2^i形式的数量（2 ^ 1,2 ^ 2,2 ^ 4,2 ^ 8等）并进行一些乘法运算（在这种情况下不再是O（1））。

Answer 6

您可以事先创建一个对数数组。这将找到最多log（N）的对数值：

#define N 100000
int naj[N];

naj[2] = 1;
for ( int i = 3; i <= N; i++ )
{
    naj[i] = naj[i-1];
    if ( (1 << (naj[i]+1)) <= i )
        naj[i]++;

}

数组naj是您的对数值。其中naj [k] = log（k）。日志基于两个。

Answer 7

这使用二进制搜索来找到最接近2的幂。

public static int binLog(int x,boolean shouldRoundResult){
    // assuming 32-bit integer
    int lo=0;
    int hi=31;
    int rangeDelta=hi-lo;
    int expGuess=0;
    int guess;
    while(rangeDelta>1){
        expGuess=(lo+hi)/2; // or (loGuess+hiGuess)>>1
        guess=1<<expGuess;
        if(guess<x){
            lo=expGuess;
        } else if(guess>x){
            hi=expGuess;            
        } else {
            lo=hi=expGuess;
        }
        rangeDelta=hi-lo;
    }
    if(shouldRoundResult && hi>lo){
        int loGuess=1<<lo;
        int hiGuess=1<<hi;
        int loDelta=Math.abs(x-loGuess);
        int hiDelta=Math.abs(hiGuess-x);
        if(loDelta<hiDelta)
            expGuess=lo;
        else
            expGuess=hi;
    } else {
        expGuess=lo;
    }
    int result=expGuess;
    return result;
}