Binary and hexadecimal

Computers store everything as bits, values that are either 0 or 1. Numbers, text, pixels, instructions: all of it ends up as strings of bits. To read those strings, you need to be comfortable with base 2 (binary) and with its shorthand, base 16 (hexadecimal). This chapter builds both from scratch.

Positional notation

The decimal number 2026 means 2 thousands, 0 hundreds, 2 tens and 6 ones:

2026 = 2×10³ + 0×10² + 2×10¹ + 6×10⁰

Each position is worth ten times the one to its right. Ten is the radix, or base. Nothing about the method depends on ten: in base b, you need b digit symbols, 0 to b − 1, and each position is worth b times the one to its right. The same works to the right of the point, with negative powers: 0.25 is 2×10⁻¹ + 5×10⁻².

The bases that matter in computing are:

When the base isn't clear from context, it's written as a subscript: 111₂ is seven, 111₁₀ is one hundred and eleven, 111₁₆ is 273.

Why binary

A circuit could in principle distinguish ten voltage levels, but it would have to tell 0.5 V from 0.6 V reliably, despite noise, temperature and manufacturing variation. Two levels, "low" and "high", with a wide safety margin between them, are far easier to build and far more robust. The digital logic level is built on exactly that: every wire carries one bit.

In binary, each position is worth twice the one to its right:

11111101010₂ = 1×2¹⁰ + 1×2⁹ + 1×2⁸ + 1×2⁷ + 1×2⁶ + 1×2⁵ + 0×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰
             = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2
             = 2026

It pays to know the first powers of two by heart:

n bits can represent 2ⁿ different values: an 8-bit byte has 256 patterns, 0 to 255 when read as an unsigned number; 16 bits give 0 to 65,535; 32 bits give 0 to 4,294,967,295. How to represent negative numbers is the subject of the two's complement chapter.

Converting decimal to binary

There are two classic methods.

Subtract powers of two. Find the largest power of two that fits, subtract it, and repeat. 2026 − 1024 = 1002; − 512 = 490; − 256 = 234; − 128 = 106; − 64 = 42; − 32 = 10; − 8 = 2; − 2 = 0. The powers used were 2¹⁰, 2⁹, 2⁸, 2⁷, 2⁶, 2⁵, 2³ and 2¹: put a 1 in those positions and 0 elsewhere, and you get 11111101010.

Divide by two repeatedly. Divide by 2 and write down the remainder; continue with the quotient until it reaches 0. The remainders, read from the last to the first, are the binary digits:

Reading upward: 11111101010. The same method works for any base: divide by 16 to get hexadecimal digits, by 8 for octal.

Going back, the fastest method by hand is doubling: start from 0, and for each bit from left to right, double the running total and add the bit. For 11111101010: 1, 3, 7, 15, 31, 63, 126, 253, 506, 1013, 2026. That's also exactly how a program parses a number from text, one digit at a time.

Fractions

To the right of the binary point, positions are worth ½, ¼, ⅛ and so on. To convert a decimal fraction, multiply by 2 repeatedly and take the integer part each time: 0.625 × 2 = 1.25, 0.25 × 2 = 0.5, 0.5 × 2 = 1.0, so 0.625 = 0.101₂ (½ + ⅛).

Many simple decimal fractions have no finite binary form. 0.1 × 2 gives 0.2, 0.4, 0.8, 1.6, 1.2, 0.4, … and the pattern repeats forever: 0.1 = 0.000110011001100…₂, just as ⅓ = 0.333… in decimal. A computer has to cut it off somewhere, which is why 0.1 can't be stored exactly. The floating-point chapter picks up from there.

Hexadecimal: four bits per digit

Long binary strings are hard to read and easy to miscopy. Hexadecimal fixes that, thanks to one property: 16 = 2⁴, so each hex digit stands for exactly four bits, and the conversion is done group by group, with no arithmetic. The digits after 9 are A (10) to F (15):

To convert binary to hex, split the bits into groups of four starting from the right, and replace each group:

2026 = 111 1110 1010₂
     =   7    E    A   = 0x7EA

And back: 0xC0FFEE is 1100 0000 1111 1111 1110 1110, 24 bits, or 12,648,430 in decimal. A byte is always exactly two hex digits, from 00 to FF, which is why hex is the standard way to show memory, machine code, network packets and file contents. The xxd tool, for example, shows the four bytes of the text "Hi!" followed by a newline:

$ printf 'Hi!\n' | xxd
00000000: 4869 210a                                Hi!.

48 is H, 69 is i, 21 is !, 0a is the newline: the character codes of the text chapter. Colors on the web (#FF8800: red 255, green 136, blue 0), memory addresses in a debugger, and the x86 instruction bytes are all written in hex for the same reason.

In the simulator, every register is displayed in both hex and decimal. Shifting left by 4 bits appends a hex zero, shifting right by 4 drops the last hex digit, and ANDing with 0xF keeps only the last one, because each hex digit is one 4-bit group:

The first three instructions load the same number, written three ways: the assembler converts them all to the same bits. After the shifts, eax is 0x7EA0 (32,416 = 2026 × 16), ebx is 0x7E (126 = 2026 ÷ 16, rounded down), and ecx is 0xA (10). The shr also sets the carry flag to 1: it's the last bit shifted out, bit 3 of 1010.

Octal

Octal does the same with groups of three bits: 2026 = 11 111 101 010₂ = 3752₈. It was popular on machines whose word size was a multiple of 3 (the 12-bit PDP-8, and 36-bit machines like the IBM 7094), where a word is a whole number of octal digits. On today's 8-, 16-, 32- and 64-bit machines, hex fits better, and octal survives mostly in one place: Unix file permissions, where each digit holds the three read-write-execute bits for the owner, the group and everyone else. chmod 755 means 111 101 101: rwxr-xr-x, which is what ls -l /bin/ls shows.

Octal also left a trap in C: a number with a leading zero is octal. int a = 010; sets a to 8. Python 3 and JavaScript's strict mode refuse the ambiguous form and require 0o10.

Bits, nibbles, bytes and words

• A bit is one binary digit.
• A nibble is 4 bits: one hex digit.
• A byte is 8 bits: two hex digits. It is the smallest unit of memory that has its own address on essentially every machine today. That wasn't always so (some early machines had 6- or 9-bit bytes), which is why networking standards say octet when they mean exactly 8 bits.
• A word is the natural size a machine computes with, usually the width of its registers: 64 bits on x86-64, ARM64 and RV64. The name is overloaded: for backward-compatibility reasons, x86 manuals still call 16 bits a "word", 32 bits a "doubleword" and 64 bits a "quadword", which is where assembly's WORD PTR, DWORD PTR and QWORD PTR come from.

How the bytes of a multi-byte word are ordered in memory is a separate question, covered in the endianness chapter. How big a kilobyte is (1,000 or 1,024 bytes) is covered in the units chapter.

In your own code

Every mainstream language can print and parse these bases:

$ python3 -c "print(f'{2026:b} {2026:o} {2026:x} {2026:#x}')"
11111101010 3752 7ea 0x7ea
$ printf '%x %o %d\n' 2026 2026 0x7ea
7ea 3752 2026

In C, printf has %x and %o (and, since C23, %b); C23 also standardized the 0b prefix for binary literals, which compilers had long accepted as an extension.

Takeaways

• In a positional system with base b, each digit is worth b times the one to its right. Computers use base 2 because two voltage levels are easy to tell apart reliably.
• n bits give 2ⁿ patterns: 256 for a byte, 65,536 for 16 bits, about 4.3 billion for 32 bits.
• Decimal to binary: subtract powers of two, or divide by 2 and read the remainders bottom to top. Binary to decimal: double and add, bit by bit. 2026 = 11111101010₂.
• Decimal fractions like 0.1 repeat forever in binary, so they can't be stored exactly.
• Hexadecimal is shorthand for binary: one hex digit = 4 bits (a nibble), two = one byte. 2026 = 0x7EA. Octal groups 3 bits and survives in Unix permissions (755) and in C's leading-zero trap.
• A word is the machine's natural size, 64 bits today, though x86 names still call 16 bits a "word".