Number Bases and Conversion

The everyday side of this subject, what binary, octal and hexadecimal are and how to convert by hand and in Python, is on Number Systems and Data Representation. This page goes one layer deeper: why the methods work, and what follows from that.

Positional notation

In positional notation a digit's value depends on where it stands. In 2026 the first 2 means two thousands and the last 6 means six ones:

The number that the powers are taken of is the radix, or base: 10 for decimal, 2 for binary, 16 for hexadecimal. A base-b system needs exactly b digits, with values 0 up to b - 1. In general, a number with digits d_{n-1} \ldots d_1 d_0 in base b is worth

"the sum, over every position i counted from the right starting at 0, of the digit at that position times the base to the power i". The rightmost position has weight b^0 = 1 in every base.

Worked example: 7EA in hexadecimal

1. The digits are 7, E and A. In hex, E = 14 and A = 10.
2. The weights, from the right, are 16^0 = 1, 16^1 = 16 and 16^2 = 256.
3. Multiply and add: 7 \cdot 256 + 14 \cdot 16 + 10 \cdot 1 = 1792 + 224 + 10 = 2026.

So 7\text{EA}_{16} = 2026_{10}; the subscript names the base.

Horner's method

Computing every power separately is wasteful. Factor out the base step by step instead:

Read the digits from left to right, and for each one: multiply what you have by the base, then add the digit. For 7EA: start at 7; 7 × 16 + 14 = 126; 126 × 16 + 10 = 2026. This is Horner's method, and it is how int(text, base) and every number parser work:

def from_base(digits, base):
    value = 0
    for d in digits:                     # Horner's method: multiply, then add
        value = value * base + int(d, 36)
    return value

print(from_base("7EA", 16), from_base("3752", 8), from_base("11111101010", 2))
print(int("7EA", 16), int("3752", 8), int("11111101010", 2))

2026 2026 2026
2026 2026 2026

int(d, 36) turns a single digit character into its value: "7" becomes 7, "E" 14 and "A" 10.

Why repeated division converts

Base conversion rewrites the same quantity with the digits of a different base. To decimal, you evaluate the sum above. From decimal to another base, the standard method divides by the base again and again and collects the remainders (the steps are shown on From decimal to another base). Why does that work? Look at the sum for a number in base b:

1. Every term except the last digit contains at least one factor b. So dividing N by b leaves remainder d_0: the remainder is the last digit, N \bmod b.
2. The quotient, \lfloor N / b \rfloor, is d_{n-1} b^{n-2} + \cdots + d_1: the same number with its last digit removed and every other digit moved one place to the right.
3. Repeat on the quotient to get d_1, then d_2, and so on, until the quotient is 0. The digits come out from right to left, which is why the remainders are read from the bottom up.

Decimal works the same way, which makes it easy to check: 2026 divided by 10 is 202 remainder 6, the last digit; 202 is 2026 with the 6 removed. For 2026 in binary:

n, steps = 2026, []
while n > 0:
    q, r = divmod(n, 2)
    steps.append(f"{n:>4} = 2 x {q:>4} + {r}")
    n = q
print("\n".join(steps))

2026 = 2 x 1013 + 0
1013 = 2 x  506 + 1
 506 = 2 x  253 + 0
 253 = 2 x  126 + 1
 126 = 2 x   63 + 0
  63 = 2 x   31 + 1
  31 = 2 x   15 + 1
  15 = 2 x    7 + 1
   7 = 2 x    3 + 1
   3 = 2 x    1 + 1
   1 = 2 x    0 + 1

Reading the remainders from the bottom up gives 11111101010_2. divmod(n, 2) returns the floor quotient and the remainder in one step (see true division and floor division). The same loop works for any base, with a digit alphabet for values above 9:

def to_base(n, base):
    digits = "0123456789ABCDEF"
    if n == 0:
        return "0"
    out = ""
    while n > 0:
        n, r = divmod(n, base)
        out = digits[r] + out
    return out

print(to_base(2026, 2), to_base(2026, 8), to_base(2026, 16))

11111101010 3752 7EA

Try it: decimal and binary

Convert a whole number to binary with the repeated division above, or a binary number back to decimal by adding place values.

Why grouping bits works

Converting between binary and hex by grouping four bits works because 16 = 2^4. Group the binary sum in blocks of four positions and factor out the powers of 16: the block at positions 4 to 7 is multiplied by 2^4 = 16^1, the block at positions 8 to 11 by 2^8 = 16^2, and each block on its own is a value from 0 to 15, exactly one hex digit. Octal works the same with blocks of three, since 8 = 2^3.

That makes binary the natural bridge between octal and hex, which do not group into each other (8 is not a power of 16):

octal         3    7    5    2
binary      011  111  101  010
regroup    0111 1110 1010
hex           7    E    A

Python's built-in conversions are summarized on Converting in Python; the most useful ones in one place:

print(int("11001000", 2), int("c8", 16), int("310", 8))
print(bin(200), oct(200), hex(200))
print(format(200, "08b"), format(200, "02X"), f"{200:#x}")
print(int("0x1F", 16), int("0b101", 0), int("0o17", 0))

200 200 200
0b11001000 0o310 0xc8
11001000 C8 0xc8
31 5 15

With base 0, int() reads the base from the prefix (0b, 0o, 0x), and with base 16 a 0x prefix is allowed too.

Other bases: 36, 64 and mixed radix

Nothing limits the base to 2, 8, 10 and 16. Three others show up in IT.

Base 36

With the digits 0–9 and the letters A–Z you have 36 symbols, the largest base Python's int() accepts. Some systems use base 36 for short, case-insensitive identifiers:

print(int("KESTREL", 36))
print(int("kestrel", 36))               # letters are case-insensitive

44430590973
44430590973

The IBAN check digits use the same letter values (A = 10 up to Z = 35), but write them side by side as decimal digits instead of computing a base-36 number; that check is on Modular Arithmetic.

Base 64

Base64 encoding turns arbitrary bytes into text that survives email and JSON. It reads the data as one long binary number and cuts it into 6-bit groups; each group, a value from 0 to 63, becomes one character (A–Z for 0–25, a–z for 26–51, 0–9 for 52–61, then + and /). Three bytes are 24 bits, which is exactly four 6-bit characters, so the encoded text is about a third larger than the data.

import base64

data = "Kes".encode("ascii")              # 3 bytes = 24 bits
print(format(int.from_bytes(data, "big"), "024b"))
print(base64.b64encode(data).decode())    # 4 characters of 6 bits each

010010110110010101110011
S2Vz

Split into sixes, the bits are 010010 110110 010101 110011, that is 18, 54, 21 and 51, which map to S, 2, V and z. Base64 is an encoding, not encryption: anyone can decode it.

Mixed radix: time

Time uses a different base per position: 60 seconds in a minute, 60 minutes in an hour, 24 hours in a day. That is a mixed-radix system, and the repeated-division method still works, as long as you divide by the right base at each step. A server that reports an uptime of 1,000,000 seconds:

1. 1000000 = 60 \cdot 16666 + 40: 40 seconds, 16,666 minutes.
2. 16666 = 60 \cdot 277 + 46: 46 minutes, 277 hours.
3. 277 = 24 \cdot 11 + 13: 13 hours, 11 days.

# Uptime in seconds -> days, hours, minutes, seconds (a mixed-radix number)
uptime = 1_000_000
minutes, seconds = divmod(uptime, 60)
hours, minutes = divmod(minutes, 60)
days, hours = divmod(hours, 24)
print(f"{days} d {hours} h {minutes} min {seconds} s")
print(((days * 24 + hours) * 60 + minutes) * 60 + seconds)

11 d 13 h 46 min 40 s
1000000

The last line converts back with Horner's method, multiplying by a different base at each step.

Binary fractions

Positions to the right of the point continue the pattern with negative powers. In decimal, 0.25 means 2 \cdot 10^{-1} + 5 \cdot 10^{-2}. A binary fraction has the weights 2^{-1} = \tfrac{1}{2}, 2^{-2} = \tfrac{1}{4}, 2^{-3} = \tfrac{1}{8} and so on after the binary point:

From a decimal fraction to binary

For the part after the point, multiply by 2 instead of dividing. Multiplying by 2 moves the binary point one place to the right, so the bit that crosses the point, the integer part of the result, is the next binary digit. Keep the fraction and repeat. Worked example, 0.625:

1. 0.625 × 2 = 1.25: first bit 1, keep 0.25.
2. 0.25 × 2 = 0.5: next bit 0, keep 0.5.
3. 0.5 × 2 = 1.0: next bit 1, keep 0. Done.
4. Read the bits from the top down: 0.101₂. (Here you read top-down, the opposite of the division method.)

Now 0.1: 0.2 (0), 0.4 (0), 0.8 (0), 1.6 (1, keep 0.6), 1.2 (1, keep 0.2), and 0.2 is where we were after the first step. The pattern 0011 repeats forever: 0.1 = 0.0\overline{0011}_2.

from fractions import Fraction

def binary_fraction(x, places):
    bits = ""
    for _ in range(places):
        x *= 2
        bits += str(int(x))
        x -= int(x)
    return "0." + bits

print(binary_fraction(Fraction(5, 8), 6))
print(binary_fraction(Fraction(1, 10), 12))
print(Fraction(0.1))

0.101000
0.000110011001
3602879701896397/36028797018963968

The last line shows the fraction a Python float actually stores for 0.1: the denominator is 2^{55}, and the value is very close to, but not exactly, one tenth. That is the root of the famous 0.1 + 0.2 surprise (see Why 0.1 + 0.2 is not 0.3 and Floating-Point Numbers).

Which fractions fit exactly?

A fraction p/q in lowest terms has a finite binary expansion exactly when q is a power of 2. The reasoning: a binary fraction with k bits after the point is a whole number divided by 2^k. So a fraction can only be written that way if its denominator divides a power of 2, and the only divisors of a power of 2 are smaller powers of 2. One tenth has denominator 10 = 2 \cdot 5, and that factor 5 can never be cancelled.

Decimal has the same problem with a different set of fractions: base 10 = 2 · 5, so a fraction terminates in decimal exactly when its denominator has no prime factors other than 2 and 5. One third repeats in both (0.333… and 0.0101…₂). Checking whether a number is a power of 2 is itself a neat bit trick, explained on Binary Arithmetic and Bitwise Operations:

from fractions import Fraction

def terminates_in_binary(fraction):
    q = fraction.denominator                 # Fraction is always in lowest terms
    return q & (q - 1) == 0                  # true only for powers of 2

for text in ("5/8", "3/4", "1/10", "1/3", "7/1024"):
    print(text, terminates_in_binary(Fraction(text)))

5/8 True
3/4 True
1/10 False
1/3 False
7/1024 True

How many digits does a number need?

With n digits in base b you can write b^n different values, from 0 up to b^n - 1. So a number N \ge 1 needs

"the logarithm of N in base b, rounded down, plus one". For 2026 in binary: \log_2 2026 \approx 10.98, rounded down 10, plus 1: 11 bits, which matches 11111101010_2. In hex: \log_{16} 2026 \approx 2.74, so 3 digits, matching 7EA. (Logarithms are explained on Powers, Roots and Logarithms.)

Because one hex digit is four bits, a value of k bits needs \lceil k/4 \rceil hex digits. Decimal digits do not line up with bits, but each bit adds about \log_{10} 2 \approx 0.301 decimal digits:

import math

for bits in (8, 32, 48, 128):
    largest = 2 ** bits - 1
    print(f"{bits:>3} bits: {math.ceil(bits / 4):>2} hex digits, "
          f"{len(str(largest)):>2} decimal digits")
print(2 ** 128)
print((2026).bit_length(), len(format(2026, "x")))

  8 bits:  2 hex digits,  3 decimal digits
 32 bits:  8 hex digits, 10 decimal digits
 48 bits: 12 hex digits, 15 decimal digits
128 bits: 32 hex digits, 39 decimal digits
340282366920938463463374607431768211456
11 3

That is why a MAC address (48 bits) is written as 12 hex digits and an IPv6 address (128 bits) as 32 hex digits in eight groups (see Writing IPv6 addresses): in decimal it would take up to 39 digits with no visible structure. int.bit_length() gives the number of bits exactly, without the rounding risk of a floating-point logarithm.

Where bases show up in IT

An IPv4 address is a positional number too. Its four octets are the digits of a base-256 number, written in decimal and separated by dots (see Dotted-decimal notation). Worked example, 192.0.2.130:

1. The weights are 256^3, 256^2, 256 and 1.
2. 192 \cdot 16777216 + 0 \cdot 65536 + 2 \cdot 256 + 130 = 3221225472 + 512 + 130 = 3221226114.
3. In hex every octet becomes exactly two digits: C0 00 02 82, so the address is 0xC0000282.

import ipaddress

a, b, c, d = 192, 0, 2, 130
print(a * 256 ** 3 + b * 256 ** 2 + c * 256 + d)
print(int(ipaddress.IPv4Address("192.0.2.130")))
print(ipaddress.IPv4Address(3221226114))
print(format(3221226114, "08X"))

3221226114
3221226114
192.0.2.130
C0000282

Other places where you meet a base other than 10:

• Hexadecimal: MAC addresses, IPv6, colors, memory addresses, hashes and Unicode code points such as U+00E9 (see Unicode and code points).
• Octal: Linux permissions, where each digit is exactly the three bits read, write and execute (see Permission bits in depth).
• Binary: subnet masks and every bitwise operation; the arithmetic itself is on Binary Arithmetic and Bitwise Operations.
• Base64: email attachments, data URLs, tokens and certificates in PEM format.