如何计算不同进制下数字的位数？

Question

我正在处理不同进制的数字（十进制，八进制，十六进制等），我试图计算每个数字中字符的数量。

示例

数字：ABCDEF 数字的位数：6 我知道有一种基于对数的方法，但我遇到了一些问题。

1.这个 Python脚本 输出说在100万个数字中有3969个没有正确地计算出数字的位数。 2.我认为使用对数的方法可能会相当慢。

链接：

• 这个C程序可能非常慢（如果我有一个非常大的数字怎么办？）。它也无法处理不同进制的数字（例如，16进制）。

• 不是这个的重复，因为那里的提问者只问了关于10进制的问题。

---

编辑：当然我可以计算字符串的长度，但我最感兴趣的是，是否可能在不使用字符串的情况下进行计算。我想知道能够帮助进行计算的算法，只知道源基数和要转换的基数。

编辑2：源基数为十进制，要转换的基数可以是任何其他基数。

---

我们如何计算不同进制下数字的位数？

如果我知道一个十进制数，如何计算转换成十六进制（八进制等）后的位数，而不用进行转换？

注意: 如果有Python或C代码会非常感激。

- ForceBru

---

在给你一个完整的答案之前，我有一个想法，这个方法是否能满足你：找到所需的幂n，例如16^n > 你的数字 > 16^n，因为这样数字的位数应该是n... - Emmanuel Jay

你是在问我们如何调试你的Python脚本吗？ - abarnert

@EmmanuelJay，我认为任何足够快的方法都可以适用。 - ForceBru

@abarnert，不用了，我觉得我自己可以处理这个问题。这个脚本是为了测试使用对数的方法而制作的。 - ForceBru

@vib，哦，是的，我忘了提到source_base是十进制，糟糕，我现在编辑... - ForceBru

Answer 1

对数本来不应该很慢。你可以通过这个公式轻松地计算任意底数的对数：logBaseN(x)=logBaseA(x)/logBaseA(N)，可使用 ln (以 e 为底数，约等于 2.718...) 或 logBase10 或你手头有的任何底数。因此，你实际上不需要一个程序，只需使用公式即可：

Translated text:

对数本来不应该很慢。你可以通过这个公式轻松地计算任意底数的对数：logBaseN(x)=logBaseA(x)/logBaseA(N)，可使用 ln (以 e 为底数，约等于 2.718...) 或 logBase10 或你手头有的任何底数。因此，你实际上不需要一个程序，只需使用公式即可：

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

其中N是您的数字，base是您希望该数字所在的进制。

如需更详细的解释，请参见此处: http://www.mathpath.org/concepts/Num/numdigits.htm

- kratenko

---

谷歌成功地将这个链接从我面前隐藏起来了，我现在要调查一下。 - ForceBru

谢谢。我猜n = 0会是一个特殊情况？ - Mattias Wadman

@MattiasWadman 当然可以。在所有进制下都是1。如果负数是一个问题，您还需要处理它，并决定在您的情况下合理的返回值是什么（对于N和-N，数字的位数相同，但为了显示，您可能需要为-添加一个额外的字符）。 - kratenko

这在实践中是行不通的，如下所示。 - smichr

Answer 2

注意你的Python代码中的NumToStr()函数存在基数偏差，需要进行修正：

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

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

通过这个修复，我们可以使用给定的公式得到正确的数字位数：

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

除了底数的准确幂次方（base**0，base**1，base**2等），其中它比应该的值少一个。这可以通过稍微改变公式来修复：

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

请注意，即使对于某些输入，这种方法似乎也会失败（例如将十进制转换为十进制时，它会错误地指出1000需要3个数字，而1000000需要6个数字）。这似乎是由于浮点数的固有不精确性造成的，例如：

print floor(log(1000, 10))

输出结果为2，而不是预期的3。

关于您提到的性能问题，我认为在您进行了性能分析和基准测试之前，不必担心这种琐碎的代码会出现性能问题。例如，对于一个128位的数字，您的“非常慢”的C代码最多只需要38次除以10。如果您需要比这更好的性能，则使用此处提到的任何琐碎方法都会遇到同样的问题。我能想到的最快的方法是使用查找表和线性插值结合的自定义log()函数，但您必须注意其精度。

- uesp

Answer 3

我不确定我理解你的问题。当你说你的初始数字是在b1进制中时，这是否意味着你有一个以b1为基数的字符串表示它？也许你想构建一张表格告诉你在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的线性。

编辑: 如果你想更快，你可以将其实现为二分查找。然后您可以获得O(log(n))。

- vib

Answer 4

这个问题比答案所暗示的要微妙一些。

>>> num_digets(1000, 10)  # there are 4 digits
3
>>> [num_digets(1000**i,10)%3 for i in range(1,10)]  # these should all be 1
[0, 0, 0, 0, 0, 0, 0, 0, 0]

def ndigits(N, b):
    if b < 2:
        raise ValueError('base must be integer greater than 1')
    n = abs(N)
    if n < b:
        return 1
    if b == 2:
        return n.bit_length()
    d = math.floor(math.log10(n)/math.log10(b))
    b_ = b**d
    while b_ <= n:  # this will iterate 0, 1 or 2 times
        d += 1
        b_ *= b
    return d

>>> [ndigits(1000**i,10)%3 for i in range(1,10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1]

这需要额外的注意，原因是math.log(1000**i)/math.log(10)比预期的浮点整数稍微小一些。

import math
>>> math.log(1000)/math.log(10)
2.9999999999999996

如果您在以10为底的情况下使用math.log10，它将按预期工作，但对于其他进制（如以5为底的125）将失败。这里是一组测试，无论您使用哪个公式：

    assert ndigits(2, 2) == 2
    assert ndigits(2**48 - 1, 2) == 48
    assert ndigits(1000, 10) == 4
    assert ndigits(125, 5) == 4
    assert ndigits(100, 16) == 2

SymPy有一个名为integer_log的函数，可以用来计算精确值，因此答案是1 + integer_log(n, b)[0]。这并不复杂，但比直接使用math.log进行计算要慢一些。

- smichr

---

（我不理解If you care are。）（您可以在这里插入一个超链接，以免让读者对num_digets()的出处感到困惑。） - greybeard