如何计算不同基数中数字的位数？

Question

我正在处理不同基数（基数 10、基数 8、基数 16 等）的数字。我正在尝试计算每个数字中的字符数。

例子

Number: ABCDEF

Number of digits: 6

我知道基于对数的方法，但我遇到了一些问题。

This Python script 输出 1,000,000 中的 3,969 个数字未能正确计算位数。
我觉得用对数的方法可能比较慢

链接：

This C program 一定很慢（如果我的数字很大怎么办？）。它也不能处理不同基数的数字（例如，base-16）。
不是 this 的骗局，因为 OP 只询问 base-10

编辑： 当然我可以计算字符串的长度，但我最感兴趣的是，是否可以在不使用字符串约定的情况下进行计算。我想知道仅知道 source-base 和 要转换为 .[=15 的基础就可以帮助实现的算法=]

Edit2: source-base 是 base-10 和 要转换为的基数 可以是任何其他基数。

如何计算不同基数的数字位数？

如果我知道 base-10 中的数字，如何在不执行转换的情况下计算转换为 base-16（base-8 等）的同一数字中的位数?

注意:一些Python或C代码将不胜感激

Answer 1

我不确定我是否理解你的问题。当您说您的初始数字在基数 b1 中时，是否意味着您将其表示为基数 b1 中的字符串？也许您想构造一些 table 来告诉您基数 b1 中的哪个数字对应于 b2、b2^2、b2^3...，然后将您的数字与这些数字进行比较以查看它适合的位置。

否则我会选择你提到的算法，它可以很容易地应用于任何基础。

输入：您的整数 x，您要计算其中数字的基数 b2。

int number_of_digits (int x, int b2) {
    int n = 0;
    while (x >0) {
        x/=b2;
        n++;
    }
    return n;
}

这两种方法都只是 n 的线性。

EDIT ：如果你想更快，你可以将其实现为二进制搜索。然后你可以得到 O(log(n)).

Answer 2

对数不应该很慢。您可以通过以下公式轻松计算任何底数的对数：logBaseN(x)=logBaseA(x)/logBaseA(N) - 您可以使用 ln(Base e = 2.718...) 或 logBase10 或任何您拥有的。所以你真的不需要一个程序，一个公式应该可以做到：

num_digets(N, base) = 1 + floor(log(N) / log(base))

其中 N 是您的号码，base 您希望该号码所在的基数。

有关更多说明，请查看此处： http://www.mathpath.org/concepts/Num/numdigits.htm

Answer 3

请注意您的 Python 代码中的 NumToStr() 函数不正确，因为您的基础中有一个差值，它应该是：

def NumToStr(num):
    str=''
    while num:
            str+=alpha[(num)%base]
            num=(num)/base
    return ''.join(list(reversed(str)))

请注意，检查此函数 returns 正确的结果会发现错误（例如，使用 alpha="0123456789"）。

通过此修复，我们可以使用给定的公式获得正确的位数：

nDigits = int(ceil(log(nmb, base)))

except 用于底数的精确幂（base**0、base**1、base**2 等...）比应有的少一分。这可以通过将 forumla 稍微更改为：

来解决

nDigits = 1 + floor(log(nmb, base))

请注意，即使这对于某些输入似乎也失败了（例如，从 base-10 转换为 base-10 它错误地表示 1000 为 3 位数字，1000000 为 6 位数字）。这似乎是由于浮点数固有的不精确性，例如：

print floor(log(1000, 10))

输出 2 而不是预期的 3.

关于您提到的性能问题，在您完成 profiling/benchmarking 表明这是一个问题之前，我不会担心此类琐碎代码的性能问题。例如，对于 128 位数字，您的 "very slow" C 代码最多只需要 38 除以 10。如果您需要比这更好的性能，那么您会运行使用这里提到的任何简单方法来解决同样的问题。我能想到的最快的事情是使用查找 table 和线性插值的组合的自定义 log() 函数，但您必须注意结果精度。

如何计算不同基数中数字的位数？

How to count the number of digits in numbers in different bases?

python

c

algorithm

base