c – 这个基地有多少位数？

问题是导出一个公式,用于确定给定十进制数在给定基数中可能具有的位数.

例如：十进制数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()可以处理这种情况吗？因此,高度赞赏这个问题的任何其他程序/公式.

编译器设置中存在快速浮动操作.您需要精确的浮动操作.问题是log10(8)/ log10(2)在数学中总是3.但可能是你的结果是2.99999,用于示例.这是坏的.您必须添加小添加剂,但不能添加0.5.它应该是大约.00001或类似的东西.

几乎真正的公式：

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

真的是真的解决方案

你应该检查你的公式的结果. Compexity是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;
}

这种检查优于使用基本乘法的暴力测试.