这个基数有多少位数?

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

以下任何一项都有效:

>>> 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 那是最小的数字 D 基准数字 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;
}

Number of digits of a numeral in a given base

由于您的公式是正确的(我刚刚尝试过),我认为这是您的除法中的舍入错误,导致数字略小于它应该是的整数值。所以当你截短为一个整数时,你会损失1。尝试在最终值中添加额外的0.5(这样截断实际上是一个圆形操作)。

你要的是上限(=最小整数不大于)对数 _乙 (n+1),而不是你现在计算的,楼层(1+对数) _乙 (n)。

你可以试试:

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

正如其他人所指出的,你有舍入误差,但所提出的解决方案只是移动危险区或缩小危险区,它们并不能消除它。如果您的数字是整数,那么您可以验证-- 使用整数算术 --底数的一次幂小于或等于数字,下一次幂大于它(第一次幂是位数)。但是,如果在链的任何地方使用浮点运算,那么您将容易出错(除非您的基数是2的幂,甚至可能是2的幂)。

编辑:
这里有一个简单但有效的整数算术解。如果integer类可以容纳与base*数字一样大的数字,这将给出正确的答案。

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

用你的公式,

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

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

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

应该解决那个问题。这和

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

因为这给出了n=8b=2的答案3,也不等于

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

因为这给出了n=7b=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);

失败(即给出答案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的整数值)时的“临界”情况。

将舍入函数(例如+0.5)包装到代码中的某个地方可能会很有好处:很可能是该部门正在生成(例如)2.99989787,其中添加了1.0,得到3.99989787,当转换为int时,得到3。

我觉得这个公式是对的:

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

所以这绝对只是一个舍入误差。

浮点舍入问题。

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

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

下面是bash中的一个解决方案:

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


% digits 10000000000 42
7

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