如何快速求二进制对数？ （最多 O(1)）

Question

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

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

最快的方法是什么？

Answer 1

答案取决于实现或语言。任何实现都可以将有效位数与数据一起存储，因为它通常很有用。如果必须计算，则找到最高有效字/分支以及该字中的最高有效位。

Answer 2

如果您使用固定宽度整数，那么其他答案已经很好地涵盖了您。

如果您使用任意大的整数，例如 Python 中的 int 或 Java 中的 BigInteger，那么您可以利用它们的可变大小表示使用底层数组的事实，因此可以使用底层数组的长度在 O(1) 时间内轻松快速地计算以 2 为底的对数。 2 的幂的以 2 为底的对数只是比表示该数字所需的位数少 1。

因此，当 n 是 2 的整数幂时：

• 在 Python 中，您可以编写 n.bit_length() - 1 (文档）。
• 在 Java 中，您可以编写 n.bitLength() - 1 (文档）。

Answer 3

我想到的最佳选择是使用二分搜索的 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;
}

请注意，此方法依赖于“位移”操作或多或少为 O(1) 的事实。如果不是这种情况，则必须预先计算 2 的所有幂或 2^2^i 形式的数字 (2^1, 2^2, 2^4, 2 ^8 等）并进行一些乘法（在本例中不是 O(1)）。

Answer 4

您可以预先创建一个对数数组。这将找到最大 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 5

这使用二分搜索来查找最接近的 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;
}

Answer 6

OP中的示例是一个65个字符的整数字符串，它不能用INT64甚至INT128表示。通过将其转换为双精度数，仍然可以很容易地从该字符串中获取 Log(2,x)。这至少可以让您轻松访问 2^1023 以内的整数。

下面您可以找到某种形式的伪代码

# 1. read the string
string="52656145834278593348959013841835216159447547700274555627155488768"
# 2. extract the length of the string
l=length(string)                         # l = 65
# 3. read the first min(l,17) digits in a float
float=to_float(string(1: min(17,l) ))
# 4. multiply with the correct power of 10
float = float * 10^(l-min(17,l) )               # float = 5.2656145834278593E64
# 5. Take the log2 of this number and round to the nearest integer
log2 = Round( Log(float,2) )             # 215

注意：

1. 某些计算机语言可以将任意字符串转换为双精度数字。因此，步骤 2,3 和 4 可以替换为 x=to_float(string)
2. 步骤 5 可以更快地完成，只需读取双精度指数（位 53 到 63）并减去 1023从它。

---

快速示例代码：如果您有awk，您可以快速测试此算法。

以下代码创建前 300 个 2 的幂：

awk 'BEGIN{for(n=0;n<300; n++) print 2^n}'

下面读取输入并执行上述算法：

awk '{ l=length($0); m = (l > 17 ? 17 : l)
       x = substr($0,1,m) * 10^(l-m)
       print log(x)/log(2)
     }'

因此，以下 bash 命令是创建从 0 到 299 的连续数字列表的复杂方法：

$ awk 'BEGIN{for(n=0;n<300; n++) print 2^n}' | awk '{ l=length($0); m = (l > 17 ? 17 : l); x = substr($0,1,m) * 10^(l-m); print log(x)/log(2) }'
0
1
2
...
299

Answer 7

快速破解：大多数浮点数表示形式会自动标准化值，这意味着它们可以有效地执行循环Christoffer Hammarström 在硬件中提到。因此，只要数字在 FP 表示的指数范围内，只需从整数转换为 FP 并提取指数就可以解决问题！ （在您的情况下，您的整数输入需要多个机器字，因此在转换中需要执行多个“移位”。）

Answer 8

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

1. 对 a[] 运行线性搜索以找到最高的a[] 中的非零 uint32_t 值 a[i]（使用 uint64_t 进行该搜索测试如果您的计算机具有本机 uint64_t 支持）

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

3. 评估 32*i+b。