草庐IT

c++ - 这个基数有多少位？

coder 2023-11-16 原文

问题是推导一个公式来确定给定十进制数在给定基数中可能具有的位数。

例如:十进制数100006可以分别用2、3、4、5、6、7、8为底的17、11、9、8、7、6、8位数字表示。

到目前为止，我得出的公式是这样的:(log10(num)/log10(base)) + 1。

在 C/C++ 中，我使用这个公式来计算上面给定的结果。

long long int size = ((double)log10(num)/(double)log10(base)) + 1.0;

但遗憾的是，在某些情况下公式没有给出正确答案，例如:

Number 8 in  base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 64 in  base 2 : 1,0,0,0,0,0,0
Number of digits: 7
Formula returned: 6

Number 64 in  base 4 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 125 in  base 5 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 128 in  base 2 : 1,0,0,0,0,0,0,0
Number of digits: 8
Formula returned: 7

Number 216 in  base 6 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 243 in  base 3 : 1,0,0,0,0,0
Number of digits: 6
Formula returned: 5

Number 343 in  base 7 : 1,0,0,0
Number of digits: 4
Formula returned: 3

所以误差是 1 位数。我只是希望有人帮我更正公式，以便它适用于所有可能的情况。

编辑: 根据输入规范，我必须处理像 10000000000 这样的情况，即 10^10，我不认为 C/C++ 中的 log10() 可以处理这种情况？因此，对于此问题的任何其他程序/公式将不胜感激。

最佳答案

您的编译器设置中有快速 float 操作。您需要精确的 float 操作。问题是 log10(8)/log10(2) 在数学上总是 3。但是，例如，您的结果可能是 2.99999。这是坏的。您必须添加少量添加剂，但不能添加 0.5。它应该大约是 .00001 或类似的东西。

几乎正确的公式:

int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);

真正的解决方案

您应该检查公式的结果。复杂度为 O(log log n) 或 O(log result)!

int fast_power(int base, int s)
{
    int res = 1;
    while (s) {
        if (s%2) {
            res*=base;
            s--;
        } else {
            s/=2;
            base*=base;
        }
    }
    return res;
}

int digits_size(int n, int base)
{
    int s = int(log10(1.0*n)/log10(1.0*base)) + 1;
    return fast_power(base, s) > n ? s : s+1;
}

此检查优于使用 base 乘法的蛮力测试。

关于c++ - 这个基数有多少位？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1847131/

amp43Numberbasecodec++calgorithmmathformula

有关c++ - 这个基数有多少位？的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 可以通过多少种方法将方法添加到 ruby​​ 对象？ - 2

    当谈到运行时自省(introspection)和动态代码生成时，我认为ruby​​没有任何竞争对手，可能除了一些lisp方言。前几天，我正在做一些代码练习来探索ruby​​的动态功能，我开始想知道如何向现有对象添加方法。以下是我能想到的3种方法:obj=Object.new#addamethoddirectlydefobj.new_method...end#addamethodindirectlywiththesingletonclassclass这只是冰山一角，因为我还没有探索instance_eval、module_eval和define_method的各种组合。是否有在线/离线资

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. ruby - 使用 Ruby，计算 n x m 数组的每一列中有多少个 true 的简单方法是什么？ - 2

    给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true？”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组，其中每个子数组代表一列，然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本，应该在1.8.6上运行，没有任何依赖:arr.transpose.map{|subarr|subarr.in

  6. ruby - 这个 ruby​​ 注入(inject)魔术是如何工作的？ - 2

    我今天看到了一个ruby​​代码片段。[1,2,3,4,5,6,7].inject(:+)=>28[1,2,3,4,5,6,7].inject(:*)=>5040这里的注入(inject)和之前看到的完全不一样，比如[1,2,3,4,5,6,7].inject{|sum,x|sum+x}请解释一下它是如何工作的？ 最佳答案 没有魔法，符号(方法)只是可能的参数之一。这是来自文档:#enum.inject(initial,sym)=>obj#enum.inject(sym)=>obj#enum.inject(initial){|mem

  7. ruby - 变量赋值后的 if 语句 - 有多常见？ - 2

    我最近与一位同事讨论了以下Ruby语法:value=ifa==0"foo"elsifa>42"bar"else"fizz"end我个人并没有看到太多这种逻辑，但我的同事指出，这实际上是一种相当普遍的Rubyism。我试着用谷歌搜索这个主题，但没有找到任何文章、页面或SO问题来讨论它，这让我相信这可能是一种非常实际的技术。然而，另一位同事发现语法令人困惑，而是将上面的逻辑写成这样:ifa==0value="foo"elsifa>42value="bar"elsevalue="fizz"end缺点是value=的重复声明和隐式elsenil的丢失，如果我们想使用它的话。这也感觉它与Ruby

  8. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  9. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  10. ruby-on-rails - ruby 新手，有人可以帮我从控制台破译这个错误吗？ - 2

    我真的只是不确定这意味着什么或我应该做什么才能让网页在我的本地主机上运行。现在它只是显示一个错误，上面写着“我们很抱歉，但出了点问题。”当我运行railsserver并在chrome中打开localhost:3000时。这是控制台输出:StartedGET"/users/sign_in"for127.0.0.1at2013-07-0512:07:07-0400ProcessingbyDevise::SessionsController#newasHTMLCompleted500InternalServerErrorin55msNoMethodError(undefinedmethod`

随机推荐