在什么时候,数字的十六进制表示占用的字符数小于小数？

Question

所以十六进制就像这样表示:0x[0..F]+ 十进制整数表示如下:[0..9]+

因此对于十进制数15,十六进制版本0xF是一个字符更长.显然这只是因为你必须添加0x,但这是编写十六进制文字的必要部分.

但是,在较大的值处,十六进制使用的字符数少于十进制数,因为它是基数16而不是十进制数.

例如

0xFFFFFFFFFFFFFFF

比...短

1152921504606846975

十六进制在什么时候变得比十进制短？是否有一个很好的小算法来计算这个数字？

我已将此标记为面试问题,即使事实并非如此.我认为这会很好.

Answer 1

表示数字n所需的某个基数B中的位数由下式给出

⌈日志_B(n + 1)⌉

这意味着十六进制数比十进制数更有效

⌈log ₁₆(N + 1)⌉<⌈log ₁₀(N + 1)⌉

如果你有一些数字n要测试,你可以将它插入这个公式,看看十六进制或十进制是否会更有效.

但是,让我们看看我们是否可以绘制出需要一些数字来表示某些内容的范围.我们在这里得到这个表:

Num Digits         Decimal Cutoff         Hex Cutoff
----------------------------------------------------
    1                   0                    0
    2                  10                   16
    3                 100                  256
    4                1000                 4096
    5               10000                65536
    6              100000              1048576
    7             1000000             16777216

请注意,当我们点击六位十进制数字时,以十进制数字编写数字永远不会更有效,因为六位数的十进制数最多为999999,六位数的十六进制数最多为16777215.所以从100000开始,你是最好用十六进制表示数字而不是十进制数字.

编辑:因为你计算0x字符作为所需的总位数的一部分,你将寻找第一个数字,其中

⌈log ₁₆(N + 1)⌉+ 2 <⌈log ₁₀(N + 1)⌉

在这种情况下,表格如下所示:

Num Digits         Decimal Cutoff         Hex Cutoff
----------------------------------------------------
    0                 100                    1
    1                1000                   16
    2               10000                  256
    3              100000                 4096
    4             1000000                65536
    5            10000000              1048576
    6           100000000             16777216
    7          1000000000            268435456
    8         10000000000           4294967296
    9        100000000000          68719476736
   10       1000000000000        1099511627776
   11      10000000000000       17592186044416

在这种情况下,两个表示相遇的点是1099511627776,它只需要11个十六进制数字但是​​13个十进制数字.从现在开始,你总是至少使用十六进制.一旦你达到10000000000000,你最好使用十六进制.

希望这可以帮助!

Answer 2

答案反复反弹很长一段时间因为10和16的力量不对齐.因此,从10的幂到16的十六进制数字串的下一个幂将暂时具有相同的长度或更短,具体取决于幅度.这是一个列出十六进制缩短位置的表:

Hex is as efficient from 1000000 to 1048575
Hex is as efficient from 10000000 to 16777215
Hex is as efficient from 100000000 to 268435455
Hex is as efficient from 1000000000 to 4294967295
Hex is as efficient from 10000000000 to 68719476735
Hex is as efficient from 100000000000 to 999999999999
Hex is more efficient from 1000000000000 to 1099511627775
Hex is as efficient from 1099511627776 to 9999999999999
Hex is more efficient from 10000000000000 to 17592186044415
Hex is as efficient from 17592186044416 to 99999999999999
Hex is more efficient from 100000000000000 to 281474976710655
Hex is as efficient from 281474976710656 to 999999999999999
Hex is more efficient from 1000000000000000 to 4503599627370495
Hex is as efficient from 4503599627370496 to 9999999999999999
Hex is more efficient from 10000000000000000 to 72057594037927935
Hex is as efficient from 72057594037927936 to 99999999999999999
Hex is more efficient from 100000000000000000 to Infinity

产生上述内容的Python脚本如下所示.它的工作原理是在每个幂上建立一个范围列表,这些值是长度可以改变的唯一值.Max将搜索限制为10 ^ max.另请注意,包含translate以剥离Python包含在特定数字以上的十六进制字符串中的L.请注意,整数只在其repr表单中附加了.通过比较日志的天花板可以避免这种Pythonic怪癖.

import math
max=25
hmax=int(math.log(10,16)*max)
f={-1:'less',0:'as',1:'more'}
r=[]
for i in sorted(map(lambda x:10**x,range(1,max))+map(lambda x:16**x,range(1,hmax))):
    r.append([cmp(len(str(i)),len(hex(i).translate(None,'L'))),i])
i=0
while i<len(r): 
    j=1
    while (i+j)<len(r) and r[i+j][0]==r[i][0]:j+=1
    end=r[i+j][1]-1 if len(r)>(i+j) else 'Infinity'
    if r[i][0]!=-1: print 'Hex is {0} efficient from {1} to {2}'.format(
        f[r[i][0]],r[i][1],end)
    i+=j