Number Systems and Data Representation

Positional number systems

In the decimal system you use every day, the position of a digit decides its value. In 472, the 4 means four hundreds, the 7 seven tens and the 2 two ones: 4 × 100 + 7 × 10 + 2 × 1. Each position is worth ten times the one to its right, because the system has ten digits (0–9). Ten is its base.

Nothing about this is special to ten. Any whole number of two or more can be a base: the number of digits equals the base, and each position is worth one power of the base more than the position to its right. Computing uses four bases.

Binary

Binary is the base-2 number system, with only the digits 0 and 1. Computers use it because their hardware is built from switches (transistors) that have two reliable states: off and on, low voltage and high voltage. Two states are easy to tell apart even with electrical noise; ten voltage levels would not be. Place values double from right to left, so binary 1011 is 8 + 0 + 2 + 1 = 11.

Hexadecimal

Hexadecimal (hex) is the base-16 number system. It needs sixteen digits, so after 0–9 it uses the letters A to F for the values 10 to 15. Hex is popular because 16 is 2⁴: one hex digit stands for exactly four bits, and two hex digits for exactly one byte. A long binary number such as 1011 0110 becomes the short, readable B6.

Octal

Octal is the base-8 number system, with the digits 0 to 7. One octal digit stands for exactly three bits. It is rarely used today, with one well-known exception: file permissions on Linux, where chmod 755 sets three groups of three permission bits (7 = 111 = read, write and execute).

Showing which base you mean

10 is ten in decimal, two in binary and sixteen in hex, so written numbers need a marker. In mathematics a subscript is used: 1011₂, B6₁₆. In code, Python, C and JavaScript all use prefixes: 0b for binary, 0x for hexadecimal and 0o for octal (C writes octal with just a leading 0, and has 0b only since C23). Hex is also often written with a trailing h, as in B6h.

Converting between number systems

From any base to decimal

Multiply each digit by its place value and add up the results. For binary, simply add the place values of the positions that hold a 1:

10110110₂ = 128 + 32 + 16 + 4 + 2 = 182. For hex it works the same way with powers of 16: B6₁₆ = 11 × 16 + 6 × 1 = 176 + 6 = 182.

From decimal to another base

Divide by the base repeatedly and write down the remainders. The remainders, read from the last to the first, are the digits. Here is 182 to binary:

182 ÷ 2 = 91  remainder 0
 91 ÷ 2 = 45  remainder 1
 45 ÷ 2 = 22  remainder 1
 22 ÷ 2 = 11  remainder 0
 11 ÷ 2 =  5  remainder 1
  5 ÷ 2 =  2  remainder 1
  2 ÷ 2 =  1  remainder 0
  1 ÷ 2 =  0  remainder 1

read upward: 10110110

An alternative that is often faster by hand: take the largest place value that fits (128), subtract it (182 − 128 = 54), and repeat with what is left (32, then 16, 4 and 2). Each place value you used gets a 1, the others a 0.

Between binary and hex (or octal)

Because one hex digit is four bits, you never need decimal in between. Split the binary number into groups of four from the right — each group of four bits is called a nibble — and replace each group with its hex digit. For octal, use groups of three.

binary  1011 0110      →  hex    B    6    = B6
binary  10 110 110     →  octal  2    6  6 = 266

Converting in Python

int() with a second argument reads a string in any base from 2 to 36. Literals with a prefix are ordinary integers:

print(int("10110110", 2))
print(int("B6", 16))
print(int("266", 8))
print(0b10110110, 0xB6, 0o266)

182
182
182
182 182 182

The other way round, bin(), oct() and hex() return strings with a prefix. format() (and f-strings) give you control over the prefix, the letter case and a fixed width with leading zeros:

n = 182
print(bin(n), oct(n), hex(n))
print(format(n, "b"), format(5, "08b"), format(n, "X"))
print(f"{n:#x} {n:#o} {5:#06b}")

0b10110110 0o266 0xb6
10110110 00000101 B6
0xb6 0o266 0b0101

Bits, bytes and units

A bit (binary digit) is the smallest unit of information: a single 0 or 1. With n bits you can make 2ⁿ different patterns: 1 bit gives 2, 4 bits give 16, 8 bits give 256.

A byte is a group of 8 bits, and the smallest unit that a computer's memory can address: every memory address points to one byte. One byte holds 256 values — 0 to 255 as an unsigned number, or 00 to FF in hex. Half a byte, 4 bits, is a nibble: exactly one hex digit.

Kilobyte or kibibyte?

For large amounts there are two systems of prefixes, and they do not agree:

• Decimal (metric) prefixes such as kilo and mega, defined by the International System of Units, step by 1000: 1 kB = 1000 bytes. Drive makers and network speeds use these.
• Binary (IEC) prefixes such as kibi and mebi step by 1024 (2¹⁰): 1 KiB = 1024 bytes. They were introduced in 1998 because "kilobyte" had long been used loosely for 1024 bytes too.

The gap grows with every step. A "1 TB" drive holds 1,000,000,000,000 bytes; Windows divides by 2³⁰ but still writes "GB", so it shows that drive as about 931 GB. No space is missing — only the units differ.

Unsigned and signed integers

A fixed number of bits can hold a fixed number of patterns, and a program decides what those patterns mean. An unsigned integer uses all patterns for zero and positive numbers: 8 bits give 0 to 255. A signed integer spends half of the patterns on negative numbers: 8 bits give −128 to 127. Both have 256 values.

Two's complement

Almost every modern computer stores signed integers in two's complement. The idea: the leftmost bit counts as a negative place value. In 8 bits, the place values are −128, 64, 32, 16, 8, 4, 2, 1. So the leftmost bit is 1 for every negative number and 0 otherwise.

To write −42 in 8-bit two's complement:

1. Write +42 in binary: 0010 1010.
2. Invert every bit (0 ↔ 1): 1101 0101.
3. Add 1: 1101 0110.

Check with the place values: −128 + 64 + 16 + 4 + 2 = −42. The same pattern, read as unsigned, is 214 (D6 in hex): the bits do not change, only their interpretation.

Why this system and not simply "one sign bit plus a value"? Because addition works without any special cases: the processor adds bits the same way for signed and unsigned numbers, and −42 + 42 gives 0000 0000 (the carry out of the eighth bit is dropped). There is also only one zero, not a +0 and a −0.

Python integers have no fixed width, but you can see the 8-bit pattern by keeping only the lowest 8 bits with the bitwise AND operator (see bitwise operators):

value = -42
bits = value & 0xFF          # keep the lowest 8 bits
print(format(bits, "08b"))
print(bits)                  # the same bits, read as unsigned
print(int.from_bytes(bytes([bits]), "big", signed=True))

11010110
214
-42

Overflow

Overflow happens when the result of a calculation is too large (or too small) for the fixed number of bits that must hold it. The bits that do not fit are lost, and the value wraps around, like a car's odometer rolling over from 999999 to 000000.

In C, the header <stdint.h> provides integer types with an exact width. uint8_t is an unsigned 8-bit integer, so it can hold 0 to 255. Counting past 255 wraps back to 0:

#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint8_t level = 250;
    for (int i = 0; i < 8; i++) {
        printf("%u ", (unsigned) level);
        level++;
    }
    printf("\n");
    return 0;
}

250 251 252 253 254 255 0 1

For unsigned types, C defines this wraparound exactly: results are taken modulo 2ⁿ. For signed types it does not: overflowing a signed integer in C is undefined behavior, meaning the program may do anything, and the compiler may assume it never happens. Overflow bugs are dangerous: they have crashed rockets (Ariane 5, 1996), and in C they are a classic cause of security holes, when a size calculation wraps to a small number and too little memory is reserved.

Python avoids the problem for integers: an int grows to as many bits as it needs, limited only by memory. You can still simulate an 8-bit counter with the modulo operator:

print(2 ** 64)
print((255 + 1) % 256)

18446744073709551616
0

Floating-point numbers

Integers cannot hold fractions, and a fixed number of digits after the point wastes bits on very large or very small values. A floating-point number stores a number in scientific notation, but in binary: a sign, a fraction (the significant digits) and an exponent that says where the binary point goes — it "floats". Almost all hardware follows the IEEE 754 standard.

A worked example: 6.5

6.5 in binary is 110.1 (4 + 2 + ½). Normalized, like scientific notation with one digit before the point, that is 1.101 × 2². IEEE 754 stores:

• the sign: 0 for positive;
• the exponent 2, plus a fixed bias of 127 (for single precision) so that no sign is needed: 129 = 10000001;
• the fraction: the bits after the point, 101, padded with zeros. The leading 1 is not stored, because a normalized number always starts with it.

Python's struct module shows the real bits:

import struct

raw = struct.pack(">f", 6.5)     # 6.5 as a 32-bit float: 4 bytes
print(raw.hex())
bits = format(int.from_bytes(raw, "big"), "032b")
print(bits[0], bits[1:9], bits[9:])

40d00000
0 10000001 10100000000000000000000

Why 0.1 + 0.2 is not 0.3

6.5 fits exactly, because it is a sum of powers of two. 0.1 is not: in binary it is 0.000110011001100…, repeating forever — just as ⅓ is 0.333… in decimal. The computer stores the nearest value that fits in 52 fraction bits, which is very slightly more than 0.1. The same happens to 0.2 and 0.3, and the tiny errors do not cancel out:

import math
from decimal import Decimal

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)
print(Decimal(0.1))                  # the exact value that is stored
print(math.isclose(0.1 + 0.2, 0.3))

0.30000000000000004
False
0.1000000000000000055511151231257827021181583404541015625
True

This is not a Python bug. Every language that uses IEEE 754 doubles gives the same result, JavaScript included:

console.log(0.1 + 0.2);
console.log(0.1 + 0.2 === 0.3);
console.log(Math.abs((0.1 + 0.2) - 0.3) < Number.EPSILON);

0.30000000000000004
false
true

Where hexadecimal shows up

Anywhere people need to read raw bytes, hex is the notation of choice, because every byte is exactly two hex digits.

• Colors on the web: #FF8800 is three bytes — red FF (255), green 88 (136), blue 00 (0) — an orange.
• MAC addresses of network cards: 00:1A:2B:3C:4D:5E is six bytes (48 bits), written as six pairs of hex digits.
• IPv6 addresses: eight groups of four hex digits, such as 2001:db8::1.
• Memory addresses in debuggers and error messages, such as 0x7ffe4b2c.
• Character codes: Unicode code points such as U+00E9 (see Character Encoding).

color = "FF8800"
red, green, blue = (int(color[i:i + 2], 16) for i in (0, 2, 4))
print(red, green, blue)

255 136 0