4

这是我在某个网站上看到的一个面试问题。

有人提到，答案涉及形成 log2() 的重复，如下所示：

double log2(double x )
{
if ( x<=2 ) return 1;
 if ( IsSqureNum(x) )
   return log2(sqrt(x) ) * 2;
 return log2( sqrt(x) ) * 2 + 1; // Why the plus one here.
}

至于复发，显然+1是错误的。此外，基本情况也是错误的。有人知道更好的答案吗？log() 和 log10() 是如何在 C 中实际实现的。

4

2 回答 2

10

也许我已经找到了面试官正在寻找的确切答案。就我而言，我会说在面试压力下得出这一点有点困难。这个想法是，假设你想找到log2(13)，你可以知道它位于3 到 4之间。还有3 = log2(8) and 4 = log2(16)，

从对数的性质，我们知道log( sqrt( (8*16) ) = (log(8) + log(16))/2 = (3+4)/2 = 3.5

现在，sqrt(8*16) = 11.3137和log2(11.3137) = 3.5。因为11.3137<13，我们知道我们想要的 log2(13) 将位于3.5 和 4之间，我们继续找到它。很容易注意到这有一个二分搜索解决方案，我们迭代到一个点，当我们的值收敛到log2()我们希望找到的值时。代码如下：

double Log2(double val)
{
    int lox,hix;
    double rval, lval;
    hix = 0;
    while((1<<hix)<val)
        hix++;
    lox =hix-1;
    lval = (1<<lox) ;
    rval = (1<<hix);
    double lo=lox,hi=hix;
   // cout<<lox<<" "<<hix<<endl;
    //cout<<lval<<" "<<rval;
    while( fabs(lval-val)>1e-7)
    {
        double mid = (lo+hi)/2;
        double midValue = sqrt(lval*rval);

        if ( midValue > val)
        {
             hi = mid;
             rval = midValue;
        }
        else{
            lo=mid;
            lval = midValue;
        }
    }
    return lo;

}
于 2011-05-16T06:56:54.850 回答
-1

好久没写纯C了，所以这里是C++（我觉得唯一的区别就是输出函数，所以你应该可以照着看）：

#include <iostream>
using namespace std;

const static double CUTOFF = 1e-10;

double log2_aux(double x, double power, double twoToTheMinusN, unsigned int accumulator) {
     if (twoToTheMinusN < CUTOFF)
       return accumulator * twoToTheMinusN * 2;
     else {
       int thisBit;
       if (x > power) {
            thisBit = 1;
            x /= power;
       }
       else
            thisBit = 0;
       accumulator = (accumulator << 1) + thisBit;
       return log2_aux(x, sqrt(power), twoToTheMinusN / 2.0, accumulator);
     }
}

double mylog2(double x) {
     if (x < 1)
       return -mylog2(1.0/x);
     else if (x == 1)
       return 0;
     else if (x > 2.0)
       return mylog2(x / 2.0) + 1;
     else
       return log2_aux(x, 2.0, 1.0, 0);
}

int main() {
     cout << "5 " << mylog2(5) << "\n";
     cout << "1.25 " << mylog2(1.25) << "\n";
     return 0;
}

函数“mylog2”执行一些简单的日志技巧来获取介于 1 和 2 之间的相关数字，然后使用该数字调用 log2_aux。

log2_aux 或多或少遵循 Scorpi0 链接到上面的算法。在每一步，您都会得到 1 位的结果。当你有足够的位时，停止。

如果你能拿到一份副本，费曼物理学讲座，第 23 期，从对日志的精彩解释开始，以及或多或少地如何进行这种转换。大大优于维基百科的文章。

于 2011-04-21T06:40:35.763 回答