В какой момент шестнадцатеричное представление чисел занимает меньше символов, чем десятичное?

Question

Таким образом, шестнадцатеричное представляется следующим образом: 0x[0..F]+ И десятичные целые числа представлены так: [0..9]+

Таким образом, для десятичного числа 15 шестнадцатеричная версия равна 0xF, что на один символ длиннее. Очевидно, это только потому, что вы должны добавить 0x, но это необходимая часть написания шестнадцатеричных литералов.

Однако при больших значениях шестнадцатеричный код использует меньше символов, чем десятичный, поскольку он является основанием 16, а не основанием 10.

1012 * Е.Г. *

0xFFFFFFFFFFFFFFF

короче

1152921504606846975

В какой момент гекс становится короче десятичного числа? Есть ли хороший маленький алгоритм, который вычисляет это число?

Я отметил это как вопрос для интервью, хотя это не так. Я думаю, что это было бы хорошо.

Answer 1

Количество цифр в некоторой базе B, необходимое для представления числа n, определяется как

& lceil; log _B (n + 1) & rceil;

Это означает, что шестнадцатеричные числа более эффективны, чем десятичные числа всякий раз, когда

& lceil; log ₁₆ (n + 1) & rceil; <& lceil; log <sub>10 (n + 1) & rceil;

Если у вас есть какое-то число 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 как часть общего количества требуемых цифр, вы будете искать первое число, где

& lceil; log ₁₆ (n + 1) & rceil; + 2 <& lceil; log <sub>10 (n + 1) & rceil;

В этом случае таблица выглядит так:

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 короче:

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, который произвел приведенное выше.Он работает путем построения списка диапазонов для каждой из степеней, которые являются единственными значениями, для которых длины могут изменяться.Макс ограничивает поиск до 10 ^ Макс.Также обратите внимание, что translate включен для удаления L, который Python включает в шестнадцатеричные строки выше определенного числа.Обратите внимание, что целые числа добавляются только в их форме 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

Answer 3

Ответ, аналогичный приведенному, только немного более избыточно написанный для удобства чтения с различными выходными данными, протестированный в Python 3.6:

import math

def cmp(a, b):
    return (a > b) - (a < b)


max=25
hmax=int(math.log(10,16)*max)+1
r=[]

# create mixed list of powers to 10/16 base

cblist1 = list(map(lambda x:10**x,range(1,max)))
cblist2 = list(map(lambda x:16**x,range(1,hmax)))
cblist3 = sorted(cblist1+cblist2) 

# create vector of len-comparison results

for i in cblist3:
    #print(str(i-1) +' ' +hex(i-1)[2:])

    r.append(cmp(len(str(i-1)),2+len(hex(i-1)[2:]))) 

    # one can delete the "2+" above for 0x-less calculation

# filter indices for relevant efficiencies for Hex-notation

same_eff = [i for i, e in enumerate(r) if e == 0]
less_eff = [i for i, e in enumerate(r) if e == -1]
more_eff = [i for i, e in enumerate(r) if e == 1]

# convert indices to relevant ranges in DEC and HEX

same_eff_rd = [[cblist3[x-1],cblist3[x]-1] for x in list(same_eff)]
same_eff_rh =[[hex(cblist3[x-1]),hex(cblist3[x]-1)] for x in list(same_eff)]

more_eff_rd = [[cblist3[y-1],cblist3[y]-1] for y in more_eff]
more_eff_rh =[[hex(cblist3[y-1]),hex(cblist3[y]-1)] for y in more_eff]

Теперь мы можем напечатать сводные результаты:

print('\n')
print('When adding the 0x prefix, Hex-notation becomes first as efficient for the DEC-range of [{0},{1}]'.format(*same_eff_rd[0]))
print('This translates into the HEX-range of [{0},{1}]'.format(*same_eff_rh[0]))
print('\n')
print('When adding the 0x prefix, Hex-notation becomes first more or at least as efficient, as of the DEC-range of [{0},{1}] and onwards'.format(*more_eff_rd[0]))
print('This translates into the HEX-range of [{0},{1}]'.format(*more_eff_rh[0]))

Или все диапазоны:

print('\n')
print('The "more efficient" ranges are in HEX: ')
print(list(more_eff_rh))
print('\n')
print('\n')
print('The "as efficient" ranges are in HEX: ')
print(list(same_eff_rh))