在Python中,如何找到整数中的位数?


当前回答

正如其他答案所示,使用log10会导致大n的错误结果,而使用len(str(…))或手动循环会导致大n的性能变慢。Jodag的答案提供了一个非常好的替代方案,它只适用于可能会使您的计算机崩溃的整数,但我们可以做得更好,甚至更快(对于n足够小的数学。Log2保证是准确的),避免使用对数,而是使用二进制:

def num_digits(n: int) -> int:
    assert n > 0
    i = int(0.30102999566398114 * (n.bit_length() - 1)) + 1
    return (10 ** i <= n) + i

让我们来分析一下。首先是奇怪的n.bit_length()。这将以二进制形式计算长度:

assert 4 == (0b1111).bit_length()
assert 8 == (0b1011_1000).bit_length()
assert 9 == (0b1_1011_1000).bit_length()

与对数不同,这对于整数来说既快速又精确。结果是,这个结果正好是(log2(n)) + 1。为了单独得到地板(log2(n)),我们减去1,因此n.bit_length() - 1。

接下来,我们乘以0.30102999566398114。这相当于log10(2)稍微舍入。这利用了对数规则,以便从地板(log2(n))计算地板(log10(n))的估计值。

现在,您可能想知道我们在这一点上可能有多差,因为尽管0.30102999566398114 * log2(n) ~ log10(n),但对于floor(0.30102999566398114 * floor(log2(n))) ~ floor(log10(n)),情况并非如此。回想一下x - 1 < floor(x) <= x,我们可以做一些快速的计算:

log2(n) - 1 < floor(log2(n)) <= log2(n)

log10(n) - 0.30102999566398114 < 0.30102999566398114 * floor(log2(n)) <= log10(n)

floor(log10(n) - 0.30102999566398114) < floor(0.30102999566398114 * floor(log2(n))) <= floor(log10(n))

请注意,floor(log10(n) - 0.30102999566398114)至少是floor(log10(n)) - 1,这意味着我们与结果最多相差1。这是最后的修正,我们检查10 ** i <= n,当结果太小时导致额外的1 +,当结果刚刚好时导致0 +。

类似于Jodag的答案,这种方法实际上对非常非常大的n无效,大约在10 ** 2 ** 52左右,其中i的误差超过-1。然而,这种大小的整数可能会使您的计算机崩溃,所以这应该足够了。

其他回答

def digits(n)
    count = 0
    if n == 0:
        return 1
    
    if n < 0:
        n *= -1

    while (n >= 10**count):
        count += 1
        n += n%10

    return count

print(digits(25))   # Should print 2
print(digits(144))  # Should print 3
print(digits(1000)) # Should print 4
print(digits(0))    # Should print 1

下面是一个体积大但速度快的版本:

def nbdigit ( x ):
    if x >= 10000000000000000 : # 17 -
        return len( str( x ))
    if x < 100000000 : # 1 - 8
        if x < 10000 : # 1 - 4
            if x < 100             : return (x >= 10)+1 
            else                   : return (x >= 1000)+3
        else: # 5 - 8                                                 
            if x < 1000000         : return (x >= 100000)+5 
            else                   : return (x >= 10000000)+7
    else: # 9 - 16 
        if x < 1000000000000 : # 9 - 12
            if x < 10000000000     : return (x >= 1000000000)+9 
            else                   : return (x >= 100000000000)+11
        else: # 13 - 16
            if x < 100000000000000 : return (x >= 10000000000000)+13 
            else                   : return (x >= 1000000000000000)+15

只有5个比较不是太大的数字。 在我的电脑上,它比数学运算快30%。Log10版本,比len(str())快5%。 好吧……如果你不疯狂地使用它,就没那么吸引人了。

下面是我用来测试/测量我的函数的一组数字:

n = [ int( (i+1)**( 17/7. )) for i in xrange( 1000000 )] + [0,10**16-1,10**16,10**16+1]

注意:它不管理负数,但适应很容易…

设数字为n,则n中的位数为:

math.floor(math.log10(n))+1

注意,这将为+ve个整数< 10e15给出正确答案。除此之外,返回类型的数学的精度限制。Log10开始起作用,结果可能相差1。我可以简单地在后面用len(str(n));这需要O(log(n))时间,相当于10的幂次迭代。

感谢@SetiVolkylany让我注意到这个限制。令人惊讶的是,看似正确的解决方案在实现细节中有警告。

这个问题已经问了好几年了,但是我已经编写了一个基准测试,其中包含了几种计算整数长度的方法。

def libc_size(i): 
    return libc.snprintf(buf, 100, c_char_p(b'%i'), i) # equivalent to `return snprintf(buf, 100, "%i", i);`

def str_size(i):
    return len(str(i)) # Length of `i` as a string

def math_size(i):
    return 1 + math.floor(math.log10(i)) # 1 + floor of log10 of i

def exp_size(i):
    return int("{:.5e}".format(i).split("e")[1]) + 1 # e.g. `1e10` -> `10` + 1 -> 11

def mod_size(i):
    return len("%i" % i) # Uses string modulo instead of str(i)

def fmt_size(i):
    return len("{0}".format(i)) # Same as above but str.format

(libc函数需要一些设置,我没有包括这些设置)

size_exp由Brian Preslopsky提供,size_str由GeekTantra提供,size_math由John La Rooy提供

以下是调查结果:

Time for libc size:      1.2204 μs
Time for string size:    309.41 ns
Time for math size:      329.54 ns
Time for exp size:       1.4902 μs
Time for mod size:       249.36 ns
Time for fmt size:       336.63 ns
In order of speed (fastest first):
+ mod_size (1.000000x)
+ str_size (1.240835x)
+ math_size (1.321577x)
+ fmt_size (1.350007x)
+ libc_size (4.894290x)
+ exp_size (5.976219x)

(声明:函数在输入1到1,000,000上运行)

下面是sys的测试结果。Maxsize: 100000 to sys.maxsize:

Time for libc size:      1.4686 μs
Time for string size:    395.76 ns
Time for math size:      485.94 ns
Time for exp size:       1.6826 μs
Time for mod size:       364.25 ns
Time for fmt size:       453.06 ns
In order of speed (fastest first):
+ mod_size (1.000000x)
+ str_size (1.086498x)
+ fmt_size (1.243817x)
+ math_size (1.334066x)
+ libc_size (4.031780x)
+ exp_size (4.619188x)

正如你所看到的,mod_size (len("%i" %i))是最快的,比使用str(i)略快,比其他方法快得多。

我的代码相同如下,我已经使用了log10方法:

from math import *

def digit_count(数量):

if number>1 and round(log10(number))>=log10(number) and number%10!=0 :
    return round(log10(number))
elif  number>1 and round(log10(number))<log10(number) and number%10!=0:
    return round(log10(number))+1
elif number%10==0 and number!=0:
    return int(log10(number)+1)
elif number==1 or number==0:
    return 1

我必须在1和0的情况下指定,因为log10(1)=0和log10(0)=ND,因此上面提到的条件不满足。但是,此代码仅适用于整数。