Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 68 ยท Number Theory

Number Bases and Representations

Convert between decimal, binary, octal and hex with division and place values, learn two's complement for negative numbers and see why 0.1 + 0.2 is not 0.3.

The number 156 is not a property of the symbols "1", "5", "6". It is a quantity, and the digits are one way of writing it down. Write the same quantity in base 2 and you get 10011100; in base 16, 9C. Computers store everything in binary, programmers read memory in hexadecimal, and the idea behind all of it, positional notation, is just a statement about remainders and powers.

In this lesson you will convert numbers between bases with two short algorithms, use Python's built-in helpers, represent negative integers with two's complement, and see why decimal fractions like 0.1 cannot be stored exactly in binary floating point. The repeated-division method is a direct use of the remainders from Modular Arithmetic.

Positional notation

In base b, a string of digits d_k ... d_1 d_0 (each between 0 and b โˆ’ 1) stands for

d_kยทb^k + ... + d_1ยทb + d_0

So 10011100 in base 2 is 1ยท128 + 0ยท64 + 0ยท32 + 1ยท16 + 1ยท8 + 1ยท4 + 0ยท2 + 0ยท1 = 156, and 9C in base 16 is 9ยท16 + 12 = 156, where the digit C stands for twelve. Every positive integer has exactly one such representation in a given base b โ‰ฅ 2 (with no leading zeros), which is a theorem you can prove by induction.

Bases you will meet

Decimal Base 10, digits 0 to 9.
Binary Base 2, digits 0 and 1.
Octal Base 8, each digit is 3 bits.
Hex Base 16, each digit is 4 bits.

Hex is popular because two hex digits describe exactly one byte.

1 / 2

Converting between bases

To base b (from an integer): divide by b repeatedly. The remainders, read from the last one to the first, are the digits. From base b: start at 0 and for each digit left to right compute value = value * b + digit. This second loop is Horner's method, and it avoids computing powers.

Python Base conversion by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The conversion of 156 to binary runs like this: 156 รท 2 = 78 remainder 0, 78 รท 2 = 39 remainder 0, 39 รท 2 = 19 remainder 1, and so on, giving the remainders 0, 0, 1, 1, 1, 0, 0, 1 which read backward are 10011100.

Bases 2, 8 and 16 are related because 8 = 2ยณ and 16 = 2โด. To go from binary to hex, group the bits in fours from the right: 1001 1100 becomes 9 and C. No arithmetic needed.

Python's built-ins

You rarely need to write your own: bin, oct and hex produce strings with a prefix, int(text, base) parses, and format specifications pad and align. Prefixes 0b, 0o and 0x also work as literals in source code.

Python Built-in conversion helpers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Fractions in other bases

A fraction works the same way with negative powers: binary 0.011 is 0/2 + 1/4 + 1/8 = 3/8. To convert a fraction to binary, multiply by 2 repeatedly; each time the integer part that appears is the next bit, and you keep only the fractional part. The process stops when the fraction becomes 0, which happens only if the denominator (in lowest terms) is a power of 2.

Python Fractions to binary, exactly

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

3/8 stops after three bits, but 1/10 produces the endless pattern 0.0001100110011... and 1/3 gives 0.010101... A decimal fraction with a factor of 5 in the denominator can never be written in finitely many binary digits. That fact is the root of the floating-point surprises below.

Two's complement

How does a computer store โˆ’5 in a fixed number of bits? Almost all modern hardware uses two's complement. With n bits, the pattern for a negative number โˆ’k is the pattern of 2โฟ โˆ’ k. In practice: write k in binary, flip all bits, add 1. For n = 8, 5 is 00000101, flipped is 11111010, plus 1 gives 11111011.

The top bit then acts as a sign: patterns 0 to 127 are the non-negative numbers 0 to 127, and 128 to 255 stand for โˆ’128 to โˆ’1. The range is โˆ’2^(nโˆ’1) to 2^(nโˆ’1) โˆ’ 1, so 8 bits cover โˆ’128 to 127. The big advantage is that addition needs no special case: add the patterns and drop the carry. This is just arithmetic modulo 2โฟ.

Python Two's complement in 8 bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python integers have unlimited size and print negative numbers with a minus sign (bin(-5) is -0b101), but masking with & 0xFF reveals the 8-bit two's complement pattern, 251. Fixed-width integers in languages like C, Java and Rust wrap around exactly this way, so 127 + 1 in a signed byte becomes โˆ’128.

Floating-point warnings

Real numbers in programs are usually stored as binary floating point: a sign, an exponent and 53 significant bits. Because 0.1, 0.2 and 0.3 have no finite binary expansion, each is stored as a nearby fraction, and tiny errors appear in arithmetic. Integers are exact; floats are approximations.

Python Why 0.1 + 0.2 is not 0.3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The stored value of 0.1 is the fraction 3602879701896397 / 36028797018963968, slightly above one tenth. Comparing floats with == is therefore a bug waiting to happen; use a tolerance such as math.isclose, or use Fraction or integer cents when exactness matters. The discrete-mathematics habit is to stay with integers and exact rationals whenever you can.

Never use floats for money. Store whole cents as integers, or use decimal.Decimal, so that sums like 0.10 + 0.20 stay exact.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is 10110 in base 2 as a decimal number?

    16 + 4 + 2 = 22.
  2. 2. How do you convert 1001 1100 (binary) to hex quickly?

    16 = 2^4, so each hex digit is exactly four bits: 1001 is 9 and 1100 is C, giving 0x9C.
  3. 3. In 8-bit two's complement, which pattern is -1?

    -1 is 2^8 - 1 = 255 = 11111111. All ones always means -1 in two's complement.
  4. 4. What range does 8-bit two's complement cover?

    The range is -2^7 to 2^7 - 1, which is -128 to 127.
  5. 5. Why does 0.1 + 0.2 == 0.3 evaluate to False?

    0.1, 0.2 and 0.3 are stored as nearby binary fractions, and the rounding errors do not cancel exactly.

Summary

  • A numeral in base b means d_kยทb^k + ... + d_0; each positive integer has a unique representation.
  • Convert to base b by repeated division (remainders are the digits); convert from base b with Horner's method.
  • Binary, octal and hex are related by powers of two: group bits in threes or fours.
  • Two's complement stores โˆ’k as 2โฟ โˆ’ k, so addition works with wrap-around and 8 bits cover โˆ’128 to 127.
  • Floats are binary approximations: compare with a tolerance, or use Fraction, Decimal or integers.

Next: Number Theory in Cryptography, putting modular arithmetic to work.