algorithm - 如何快速找到二进制对数？（最多为 O(1)）

Question

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

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

最快的方法是什么？

Answer 1

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

Answer 2

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

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

2. 应用bit twiddling hack来查找您在步骤 1 中找到b的uint32_t值的二进制日志。a[i]

3. 评估32*i+b。

Answer 3

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

Answer 4

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

如果您使用任意大的整数，例如int在 Python 或BigIntegerJava 中，那么您可以利用它们的可变大小表示使用底层数组这一事实，因此可以在 O( 1）时间使用底层数组的长度。2 的幂的以 2 为底的对数只是比表示数字所需的位数少一。

那么什么时候n是 2 的整数幂：

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

Answer 5

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

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

我头顶上的最佳选择是使用二进制搜索的 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 8

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. 只需读取双精度指数（第 53 位到第 63 位，包括第 63 位）并从中减去 1023，可以更快地完成第 5 步。

---

快速示例代码：如果你有awk，你可以快速测试这个算法。

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

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