At what point do hexadecimal representations of numbers take up less chars than decimals?

Question

So hexadecimal is represented like this: 0x[0..F]+ And decimal integers are represented like this: [0..9]+

So for the decimal number 15, the hex version is 0xF which is one character longer. Obviously this is only because you have to add the 0x, but that is a necessary part of writing hex literals.

However, at large values, hex uses fewer characters than decimal as it is base 16, rather than base 10.

E.g.

0xFFFFFFFFFFFFFFF

is shorter than

1152921504606846975

At what point does hex become shorter than decimal? Is there a nice little algorthm that calculates this number?

I have tagged this as an interview question even though it isn't. I think it would make a good one.

That's a simple linear relationship that you ought to be able to solve in two or three lines. The slope is the ratio of the logarithm of the bases. — Kerrek SB
Hexadecmal numbers do not start with a 0x, thats just so your complier/interpreter can identify them as Hex, in Delphi its $, in CSS its # — Dampsquid
Yes, I realise that. However it is the normal convention to put 0x before hex numbers. For my purposes, it's required. — Nick Brunt

templatetypedef templatetypedef · Accepted Answer · 2012-02-27T00:21:47

The number of digits in some base B necessary to represent a number n is given by

⌈log_B(n + 1)⌉

This means that hexadecimal numbers are more efficient than decimal numbers whenever

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

If you have some number n to test, you can just plug it into this formula to see whether hexadecimal or decimal will be more efficient.

But let's see if we can plot out the ranges where you need some number of digits to represent something. We get this table here:

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

Notice that when we hit six decimal digits, it's never more efficient to write the number in decimal, since a decimal number with six digits is at most 999999 and a hexadecimal number with six digits is at most 16777215. So from 100000 onward, you are better off writing the number in hexadecimal than in decimal.

EDIT: Because you are counting the 0x characters as part of the total number of digits required, you're going to be looking for the first number where

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

In this case, the table looks like this:

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

In this case, the point at which the two representations meet is 1099511627776, which requires only 11 hex digits but 13 decimal digits. From this point forward, you are always at least as well off using hexadecimal. Once you hit 10000000000000, you are strictly better off using hex.

Hope this helps!

At what point do hexadecimal representations of numbers take up less chars than decimals?

3 Answers