Number systems: positional systems and binary

A clock face shows IX, a book chapter begins with XIV, and a computer’s memory holds 1001. All three are numbers, just written in different “languages”. And 101 does not always mean “one hundred and one”: in decimal it does, in binary it is 5. To know the value of a number, you must know which number system it is written in. In this lesson you will learn how number systems are built, how to convert from any base to decimal and from decimal to binary, and how to solve the “count the 0s and 1s” problems that often appear in DİM entrance exam tasks.

Non-positional systems: Roman numerals

The simplest non-positional system is counting with sticks: ||||| = 5. The best known is Roman numerals: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. In XX both X’s still mean 10: a symbol does not become ten times bigger when it moves left. The rules: symbols are usually written from largest to smallest and added; a smaller symbol in front of a larger one is subtracted (only in the pairs IV, IX, XL, XC, CD, CM); the same symbol is not written more than three times in a row, and V, L and D are never repeated.

Positional systems: the base and the expanded form

In a positional system each digit has two properties: its own value and the place it stands in. The number of digits a system uses is its base (b). A base-b system uses the digits 0, 1, …, b − 1, and the place values grow from right to left as 1, b, b², b³, … The base is written as a small subscript: 352₆, 1101₂. Tasks usually name a system by its base: “base 2”, “base 8”, “base 16”. In every system the base itself is written as 10: 10₂ = 2, 10₆ = 6. Digits can also be letters: the set {0, 1, 2, k, m} has 5 digits, so it is a base-5 system (k = 3, m = 4); such problems are solved in detail in “Number systems: problems with an unknown base”.

The expanded form gives two useful results. The largest k-digit number has all its digits equal to b − 1: add 1 and you get 1 followed by k zeros, that is bᵏ. The smallest k-digit number is 1 followed by k − 1 zeros, that is bᵏ⁻¹.

Decimal to binary and back

The binary system has only two digits, 0 and 1, and its place values are the powers of two. This is the system a computer works in: one place is one bit. Knowing the table below by heart speeds up every number-system problem.

1. 1
   Divide

   Divide the number by 2 and write down the whole quotient and the remainder (0 or 1).

2. 2
   Repeat

   Divide the quotient by 2 again; keep going until the quotient is 0.

3. 3
   Read from bottom to top

   Write the remainders from the last one to the first: the first remainder is the lowest place.

4. 4
   Check

   Add the place values of the 1s — you must get the original number.

Fractions in binary

The places after the point have the values b⁻¹, b⁻², b⁻³, …; in binary these are ½ = 0.5, ¼ = 0.25, ⅛ = 0.125, 1/16 = 0.0625. To convert a decimal fraction to binary, multiply the fractional part by 2 again and again: the whole part of each product (0 or 1) is the next digit, and the fractional part is multiplied again. This time the digits are read from top to bottom. The whole part is converted separately by division.

Counting digits, 0s and 1s in binary

DİM tasks often ask: how many digits does the binary form of a number have, and how many 1s and 0s are in it? You do not need to convert the number fully — it is enough to write it as a sum of different powers of two. Each power gives one 1, the largest power fixes the length, and all the other places are 0.

A program can do the same count: divide the number by 2 and look at the remainder at every step. In a written exam task the number is typed on the keyboard, so the first line is n = int(input()); here we set n = 300 so the program runs in the browser. Harder cases (squares, 2ⁿ − 2ᵐ) are in the lesson “Number systems: problems with an unknown base”.

n = 300
ones = 0
zeros = 0
while n > 0:
    if n % 2 == 1:
        ones = ones + 1
    else:
        zeros = zeros + 1
    n = n // 2
print(ones, zeros)

4 5

Next: in “Octal and hexadecimal number systems” you will learn to write binary numbers compactly, and in “Arithmetic in different number systems” to calculate in columns in these systems.