在这个进位制中有多少个数字？

Question

问题是推导一个公式来确定在给定进制下一个十进制数可以有多少位数字。

例如：十进制数100006在二进制、三进制、四进制、五进制、六进制、七进制和八进制中分别可以用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

所以错误在于一个数字。我希望有人能帮助我纠正公式，使其适用于所有可能的情况。

编辑：根据输入规范，我必须处理像10000000000这样的情况，即10^10，我不认为C/C++中的log10()可以处理这样的情况？因此，对于此问题的任何其他过程/公式都将受到高度赞赏。

- whacko__Cracko

---

看起来你在边缘情况下出现了一个偏移一的问题。 - StrixVaria

我曾经在学校用计算器做过这个；我忘记了当时使用的公式，但当我学到 log() 函数时，我惊讶地发现它更简单！ - PP.

是的，但无法找出所需的修改。 - whacko__Cracko

int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.000001); - Alexey Malistov

这不是我的作业 + 公式标签是必要的，因此回滚! - whacko__Cracko

Answer 1

你的编译器设置中有快速浮点运算。你需要精确的浮点运算。问题在于，在数学中，log10(8)/log10(2)总是3。但是你的结果可能是2.99999，例如。这很糟糕。你必须添加一个小的加法，但不是0.5。应该是大约0.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乘法进行暴力测试更好。

- Alexey Malistov

---

谢谢，但如果num = 10000000000l怎么办？我认为log10()无法处理这种情况，还有其他解决方案吗？ - whacko__Cracko

+1，我还没有使用编译器检查你的解决方案，但我认为它会很好地工作。我喜欢你的方法。虽然我知道O(logn)的指数运算，但不知道它在这里的用途，所以谢谢 :) - whacko__Cracko

我接受你的解决方案，因为它解决了编辑前和编辑后的两个问题。 - whacko__Cracko

Answer 2

以下两种方法都可以：

>>> from math import *
>>> def digits(n, b=10):
...     return int(1 + floor(log(n, b))) if n else 1
...
>>> def digits(n, b=10):
...     return int(ceil(log(n + 1, b))) if n else 1
... 

第一个版本的解释可以在 mathpath.org 上找到。第二个版本中，+1 是必要的，以便为任何在基数为b时具有d位数字的最小数字n产生正确的答案。也就是说，在基数为b时写成10...0的数字。请注意，输入0必须被视为特殊情况。

十进制示例：

>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3

二进制：

>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11

编辑：原帖作者指出log解决方案可能无法处理大量输入。我不确定这一点，但如果是这样，下面的代码应该不会崩溃，因为它仅使用整数运算（这次是用C语言编写）：

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 0;
  while (d++, n /= b);
  return d;
}

这段代码可能效率较低。是的，它是为了最大化的晦涩程度而编写的。它简单地使用了每个数字至少有一个数字的观察结果，并且每个不能被 b 整除的除法都意味着存在额外的数字。以下是更易读的版本：

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 1;
  while (n /= b) {
    d++;
  }
  return d;
}

- Stephan202

---

这在较大的数字上失败--对我来说digits(1027,2)，但它可能取决于具体实现。 - Beta

@Beta: 在Python中，log似乎接受任意大的数字（好吧，我输入了很多位数它仍然可以工作）。 - Stephan202

但它返回多少位数字？我对Python一无所知，但我敢打赌我们可以找到两个数字b^p和（b^p）-1，它们在Python中具有相同的对数。 - Beta

Python自动切换到任意精度算术；log始终正确。但是floor和ceil不正确：至少在我的电脑上，打印出前20个10的幂的数字(n)会显示错误。（第一个版本中有两个3，在第二个版本中有两个15。）对于C版本：为什么在for循环中使用逗号分隔语句和空主体的技巧？你可以将其中一个移出来以提高清晰度。或者，如果不追求清晰度，可以更简短地写成："while(n/=b) d++;" :-) - ShreevatsaR

我还没有完全分析你的第二个解决方案，但是粗略地看，我觉得你只是计算了整个数字的基本表示，这并不是很有效率的 :) - whacko__Cracko

Answer 3

在给定进制下计算数字的位数

。这篇文章解释了如何计算在不同进制下数字的位数。

- Daniel Daranas

Answer 4

由于你的公式是正确的（我刚试过），我认为这是你在除法中发生了四舍五入误差，导致数字略微小于它应该是的整数值。因此，当你将其截断为整数时，你就会失去1。尝试在最终值上添加额外的0.5（以便截断实际上是一个四舍五入操作）。

- Nick Lewis

---

你的意思是这个：size = ((((double)log10(num) / (double)log10(base))) + 1.0)+ 0.5;？那么它不会起作用。 - whacko__Cracko

如果您再加上0.5，那么在其他边界情况下会得到不同的答案： 二进制中数字15表示为1,1,1,1 (log10(15) / log10(2)) + 1.5 = 5.407..，因此答案应该是5，而不是4。 - catchmeifyoutry

@kigurai：size = ceil((log10(num) / log10(base)) + 1.0); 这个不行！！ - whacko__Cracko

正确的公式是 floor(log10(num)/log10(base)+1.0)。然而，在初始除法中存在舍入误差，该公式在实践中并不一定有效。因此，您需要在接近整数的某个 epsilon 范围内进行四舍五入，然后再向下取整，因为有些除法会正确地给出非整数答案。 - Nick Lewis

@debanjan，是的，我注意到它在n=7和base=2时不起作用。 - Hannes Ovrén

Answer 5

你需要的是天花板函数，即不大于log_b(n+1)的最小整数，而不是你目前正在计算的地板函数，即floor(1+log_b(n))。

你可以尝试这样计算：

int digits = (int) ceil( log((double)(n+1)) / log((double)base) );

- Managu

---

当然，如果n<=1，这个方法就会失效。如果你想要更加彻底，你可以将n=0,1作为特殊情况处理。 - Managu

这还不够，因为当 n = 100 和 base = 10 时，它仍会产生 2。 - Stephan202

如果编译器设置中存在快速浮点运算，且n=7，base=2，则此代码无法正常工作。log10(8)/log10(2)约为3(2.9999或3.000001)，而ceil(3.00001)有时可能是4。 - Alexey Malistov

Answer 6

使用您的公式，

log(8)/log(2) + 1 = 4

问题在于对数计算的精度。使用

ceil(log(n+1)/log(b)) 

应该解决那个问题。这与之前不太一样。

ceil(log(n)/log(b)) 

因为当n=8，b=2时，这会得到答案3，但它并不相同。

log(n+1)/log(b) + 1

因为这个计算可以得出 n=7 b=2 时的答案为4（在完全精度下计算）。

实际上，我使用 g++ 实现和编译第一种形式时得到了一些奇怪的结果：

double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);

失败了（IE 给出了答案 3），而

double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);

成功（返回答案为4）。看起来还有第三种形式。

ceil(log(n+0.5)/log(b)) 

会更加稳定，因为它避免了 n（或第二种形式的 n+1）是 b 的整数幂（对于整数值的 n）时出现“关键”情况。

- Adam Bowen

---

你的对数函数精度是多少？ - Beta

我正在使用一个JavaScript计算器，它可以为第一个表单提供正确的答案。我认为sixlettervariables得到错误答案的原因是由于表示最终结果时出现了问题。特别地，log(8)/log(2)恰好等于3（2^3 = 8），因此log(8)/log(2)+1具有预期值4。 - Adam Bowen

Answer 7

正如其他人指出的那样，您存在舍入误差，但是提出的解决方案只是将危险区域移动或缩小，而不能消除它。如果您的数字是整数，则可以使用整数算术验证一个基数的幂小于或等于您的数字，并且下一个幂高于它（第一个幂是数字的位数）。但是，如果在任何链中使用浮点算术，则会容易受到误差的影响（除非您的基数是2的幂，甚至可能也不行）。

编辑：
这里是一种粗糙但有效的整数算术解决方案。如果您的整数类可以容纳像base*number这样大的数字，则可以得到正确的答案。

  size = 0, k = 1;
  while(k<=num)
    {
      k *= base;
      size += 1;
    }

- Beta

Answer 8

看起来这个公式对我来说是正确的：

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

log10(8) = 0.903089
log10(2) = 0.301029

Division => 3

+1 => 4

所以这肯定只是一个四舍五入误差。

- Jerod Venema

Answer 9

浮点数舍入问题。

log10(216) / log10(6) =  2.9999999999999996

但是你不能像建议的那样添加0.5，因为它对以下内容不起作用

log10(1295) = log10(6) = 3.9995691928566091   //    5, 5, 5, 5
log10(1296) = log10(6) = 4.0                  // 1, 0, 0, 0, 0

也许使用log(value, base)函数可以避免这些舍入误差。

- Didier Trosset

Answer 10

这是一个bash的解决方案：

% digits() { echo $1 $2  opq | dc | sed 's/ .//g;s/.//' | wc -c; }


% digits 10000000000 42
7

- mouviciel