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

Question

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

例如：十进制数 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() 都不能处理这种情况？因此，对于这个问题的任何其他程序/公式都将受到高度赞赏。

score 8 · Accepted Answer

您的编译器设置中有快速浮动操作。您需要精确的浮动操作。问题是 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乘法的蛮力测试。

score 7 · Accepted Answer

以下任一方法都可以：

>>> 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有必要为任何数字n产生正确的答案，该数字是以b为底的d位的最小数字。也就是说，那些以10...0为底的数字b。请注意，输入必须被视为特殊情况。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

编辑：OP 声明该log解决方案可能不适用于大量输入。我不知道，但如果是这样，下面的代码不应该分解，因为它只使用整数算术（这次在 C 中）：

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

此代码可能效率较低。是的，它是为最大模糊点而写的。它简单地使用了每个数字至少有一个数字的观察，并且每个b不产生的除法都0意味着存在一个额外的数字。更易读的版本如下：

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

score 5 · Accepted Answer

5

给定基数中数字的位数

于 2009-12-04T14:08:05.080 回答

score 3 · Accepted Answer

由于您的公式是正确的（我刚刚尝试过），我认为这是您的除法中的舍入错误，导致数字略小于应有的整数值。因此，当您截断为整数时，您会失去 1。尝试将额外的 0.5 添加到最终值（这样截断实际上是一个舍入操作）。

score 2 · Accepted Answer

你想要的是上限（=不大于的最小整数）log _b（n+1），而不是你现在正在计算的，下限（1+log _b（n））。

你可以试试：

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

score 1 · Accepted Answer

使用你的公式，

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 的整数值）时的“关键”情况。

score 1 · Accepted Answer

正如其他人指出的那样，您有舍入误差，但建议的解决方案只是移动危险区域或使其更小，它们并没有消除它。如果您的数字是整数，那么您可以验证 -使用整数算术- 底数的一个幂小于或等于您的数字，下一个在它之上（第一个幂是位数）。但是，如果您在链中的任何地方使用浮点运算，那么您将很容易出错（除非您的基数是 2 的幂，甚至可能是这样）。

编辑：
这是整数算术中粗略但有效的解决方案。如果您的整数类可以容纳与 base*number 一样大的数字，那么这将给出正确的答案。

  大小 = 0，k = 1；
  而（k<=num）
    {
      k *= 基数；
      大小 += 1；
    }

score 0 · Accepted Answer

将舍入函数（例如 + 0.5）包装到您的代码中的某处可能是有益的：除法很可能产生（例如）2.99989787，在其中添加 1.0，得到 3.99989787，当它转换为 int 时，它给出3.

score 0 · Accepted Answer

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

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

所以这绝对只是一个四舍五入的错误。

score 0 · Accepted Answer

浮点舍入问题。

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) 函数可以避免这些舍入错误。

score 0 · Accepted Answer

0

我认为消除舍入误差而不产生其他错误的唯一方法是使用或实现整数对数。

于 2009-12-04T15:01:37.620 回答

score 0 · Accepted Answer

这是 bash 中的一个解决方案：

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


% digits 10000000000 42
7

score 0 · Accepted Answer

static int numInBase(int num, int theBase)
{
   if(num == 0) return 0;
   if (num == theBase) return 1;
   return 1 + numInBase(num/theBase,theBase);
}

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

13 回答 13

Related

Reference