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
Number systemDefinition
A set of rules for writing and reading numbers with signs called digits. In a non-positional system the value of a digit does not depend on where it stands in the number; in a positional system it does.
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.
Think of Roman numerals as coins: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. A number is the total of the coins in a purse: XXVI = 10 + 10 + 5 + 1 = 26. A coin is worth the same wherever it lies — X is 10 everywhere, and that is exactly what a non-positional system means. There is just one twist: if a smaller coin stands before a larger one, it is taken away: IV = 5 − 1 = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900. And one more rule: the same symbol is not written more than three times in a row (4 is IV, not IIII), and V, L and D are never repeated.
The coin method
Problem
Read MCDXLIV.
Show solutionHide solution
Solution
M = 1000
CD: C is smaller than D → 500 − 100 = 400
XL: 50 − 10 = 40
IV: 5 − 1 = 4
Total: 1000 + 400 + 40 + 4 = 1444.
Roman numerals
Problem
1) Write MMXXVI, XLIX and CDXCIV in the decimal system.
2) Write 1994 in Roman numerals.
Show solutionHide solution
Solution
XLIX = XL + IX = (50 − 10) + (10 − 1) = 40 + 9 = 49.
CDXCIV = CD + XC + IV = 400 + 90 + 4 = 494.
2) Split the number into place values: 1994 = 1000 + 900 + 90 + 4 = M + CM + XC + IV = MCMXCIV.
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”.
Compare a positional system with counting on your fingers. In decimal you run out of digits after 9: at 9 + 1 the ones place “fills up”, you write 0 there, and 1 moves left into the tens place: 10. Now imagine counting on one hand only: the digits are 0, 1, 2, 3, 4 (5 digits — the system’s base is b = 5). At the fifth finger the hand is full: you put one pebble aside (one “five”) and start again, so five is written 10₅ and seven 12₅. Binary has only two digits, 0 and 1, so a place fills up every two units. In every system the base itself is written as 10, and the place values from right to left are 1, b, b², …
| Decimal | Base 5 | Binary |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 10 |
| 3 | 3 | 11 |
| 4 | 4 | 100 |
| 5 | 10 | 101 |
| 6 | 11 | 110 |
| 7 | 12 | 111 |
| 8 | 13 | 1000 |
Where
- N
- the value of the number in decimal
- b
- the base of the system (b ≥ 2)
- aᵢ
- the digit in place i, 0 ≤ aᵢ ≤ b − 1
- k
- the number of the highest place: number of digits − 1
The expanded form of a number. Places are numbered from right to left starting at 0. Working out this sum converts a number from any base to decimal.
From any base to decimal
Problem
Convert to decimal: 1) 1203₄; 2) 352₆; 3) 2011₃.
Show solutionHide solution
Solution
1) 1203₄ = 1·4³ + 2·4² + 0·4 + 3 = 64 + 32 + 0 + 3 = 99.
2) 352₆ = 3·6² + 5·6 + 2 = 108 + 30 + 2 = 140.
3) 2011₃ = 2·3³ + 0·3² + 1·3 + 1 = 54 + 0 + 3 + 1 = 58.
Number the places
Start from 0 on the right: in 321₄ the 1 is in place 0, the 2 in place 1 and the 3 in place 2.
Write the place values
The place values are powers of the base: 4⁰ = 1, 4¹ = 4, 4² = 16.
Multiply and add
3·16 + 2·4 + 1·1 = 48 + 8 + 1 = 57.
Check
Every digit must be smaller than the base: 3, 2, 1 < 4 ✓
The expanded form can be grouped differently — this is Horner’s scheme: N = (…((aₖ·b + aₖ₋₁)·b + aₖ₋₂)·b + …)·b + a₀. Start on the left: multiply by the base, add the next digit, and repeat. No powers need to be computed, and there is one multiplication fewer than there are digits — this is how programs convert numbers. The same form proves why the division method works: N = b·Q + a₀ with 0 ≤ a₀ ≤ b − 1, where Q is the number without its last digit. So dividing N by b leaves the remainder a₀ and the quotient Q, and repeating the division drops the digits off one by one from right to left.
With Horner’s scheme
Problem
Convert to decimal with Horner’s scheme: 1) 2011₃; 2) 110101₂.
Show solutionHide solution
Solution
2) 1 → 1·2 + 1 = 3 → 3·2 + 0 = 6 → 6·2 + 1 = 13 → 13·2 + 0 = 26 → 26·2 + 1 = 53.
In binary Horner’s scheme becomes “double and add the digit” — easy to do in your head.
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ᵏ⁻¹.
Where
- k
- the number of digits
- b
- the base
The largest and the smallest k-digit numbers in base b. There are bᵏ − bᵏ⁻¹ = (b − 1)·bᵏ⁻¹ such numbers.
The largest and the smallest numbers
Problem
1) Write the largest and the smallest three-digit numbers in base 5 and convert them to decimal.
2) How many four-digit numbers are there in binary?
3) Is 285₈ a valid number?
Show solutionHide solution
Solution
2) From 1000₂ = 8 to 1111₂ = 15: 2⁴ − 2³ = 8 numbers.
3) No: base 8 uses the digits 0–7, there is no digit 8.
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.
| n | 2ⁿ | n | 2ⁿ |
|---|---|---|---|
| 0 | 1 | 6 | 64 |
| 1 | 2 | 7 | 128 |
| 2 | 4 | 8 | 256 |
| 3 | 8 | 9 | 512 |
| 4 | 16 | 10 | 1024 |
| 5 | 32 | 11 | 2048 |
Divide
Divide the number by 2 and write down the whole quotient and the remainder (0 or 1).
Repeat
Divide the quotient by 2 again; keep going until the quotient is 0.
Read from bottom to top
Write the remainders from the last one to the first: the first remainder is the lowest place.
Check
Add the place values of the 1s — you must get the original number.
The division method has a simple meaning. Pack 13 sweets in pairs: you get 6 pairs and 1 sweet is left over — so the ones place holds 1. Then put the 6 pairs into boxes of two pairs: 3 boxes, nothing left — the twos place holds 0. Pair up the 3 boxes again: 1 big box and 1 left over — the fours place holds 1. Finally 1 big box remains — the eights place holds 1. Read the leftovers from bottom to top: 13 = 1101₂ = 8 + 4 + 1.
Where
- q
- the whole quotient
- r
- the remainder — the last digit of the number in base b
The division method works for any base: divide by b. A quick consequence: a binary number ending in 0 is even, one ending in 1 is odd.
Converting to and from binary
Problem
1) Convert 77 to binary.
2) Convert 110101₂ to decimal.
3) Convert 200 to binary by splitting it into powers of two.
Show solutionHide solution
Solution
38 ÷ 2 = 19, remainder 0
19 ÷ 2 = 9, remainder 1
9 ÷ 2 = 4, remainder 1
4 ÷ 2 = 2, remainder 0
2 ÷ 2 = 1, remainder 0
1 ÷ 2 = 0, remainder 1
From bottom to top: 77 = 1001101₂. Check: 64 + 8 + 4 + 1 = 77 ✓
2) Add only the place values of the 1s: 110101₂ = 32 + 16 + 4 + 1 = 53.
3) The largest power not exceeding 200 is 128: 200 − 128 = 72; 72 − 64 = 8; 8 − 8 = 0.
200 = 2⁷ + 2⁶ + 2³ = 11001000₂.
Interactive
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.
Think of the places after the point as slices of a pizza: the first place is a half (½), the second a quarter (¼), the third an eighth (⅛). For example, 0.11₂ = ½ + ¼ = 0.75. To turn a decimal fraction into binary, keep multiplying the fractional part by 2: if the whole part of the product is 1, the next digit is 1; if it is 0, the digit is 0; then carry on with the fractional part. These digits are read from top to bottom. The whole part is converted separately, by dividing by 2.
Convert 0.375 to binary
Problem
Convert the fraction 0.375 to binary.
Show solutionHide solution
Solution
0.75 · 2 = 1.5 → 1 (0.5 is left)
0.5 · 2 = 1.0 → 1 (nothing is left, stop)
Top to bottom: 0.375 = 0.011₂. Check: ¼ + ⅛ = 0.25 + 0.125 = 0.375 ✓
Converting fractions
Problem
1) Convert 0.1011₂ to decimal.
2) Convert 5.75 to binary.
Show solutionHide solution
Solution
2) Whole part: 5 = 101₂.
Fractional part: 0.75 · 2 = 1.5 → 1; 0.5 · 2 = 1.0 → 1; the fractional part is 0, stop.
Top to bottom: 0.75 = 0.11₂.
Answer: 5.75 = 101.11₂. Check: 4 + 1 + 0.5 + 0.25 = 5.75 ✓
Which fractions are finite in binary? A reduced fraction p/q has a finite base-b form exactly when every prime factor of q is also a factor of b. The only prime factor of 2 is 2, so in binary only fractions whose denominator is a power of 2 are finite. 0.1 = 1/10 and 10 = 2 · 5 — the factor 5 makes the form infinite. A computer keeps such numbers with a limited number of binary digits: a “double-precision” number (the IEEE 754 standard) has 53 significant bits, and the last one is rounded.
Finite or infinite?
Problem
Which of these are finite in binary: 3/8, 1/5, 7/16, 0.3? Write the finite ones in binary.
Show solutionHide solution
Solution
1/5: there is a 5 in the denominator → infinite: 0.001100110011…₂ (the group 0011 repeats).
7/16: 16 = 2⁴ → finite: 7/16 = ¼ + ⅛ + 1/16 = 0.0111₂.
0.3 = 3/10: 10 has the factor 5 → infinite.
Interestingly, in base 3 the fraction 1/3 = 0.1₃ is finite while ½ = 0.111…₃ is infinite: being finite depends on the base, not on the number.
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.
Where
- n
- the exponent
Number of 0s = number of digits − number of 1s. For example, 2⁹ − 1 = 511 = 111111111₂ — nine 1s.
Where
- N
- a natural number
- k
- the number of digits of N in binary
If this holds, N has exactly k binary digits. For example, 512 ≤ 1000 < 1024, so 1000 = 1111101000₂ has ten digits.
The inequality 2ᵏ⁻¹ ≤ N < 2ᵏ can be written with a logarithm: k = [log₂N] + 1, where [x] is the whole part of x. Other bases work the same way: for example, the number of decimal digits of N is [lg N] + 1. This formula finds the “length” of huge numbers without converting them.
How long are big numbers?
Problem
1) How many digits does 10⁹ have in binary? 2) How many decimal digits does 2¹⁰⁰ have (lg 2 ≈ 0.30103)?
Show solutionHide solution
Solution
2) lg 2¹⁰⁰ = 100 · lg 2 ≈ 30.103 ⇒ [30.103] + 1 = 31 digits.
Shortcut: 2¹⁰ = 1024 ≈ 10³, so every 10 binary digits are worth about 3 decimal digits.
A DİM-style closed task
Problem
In the binary form of 300, how many more 0s are there than 1s?
A) 1 B) 2 C) 3 D) 4 E) 5
Show solutionHide solution
Solution
300 = 2⁸ + 2⁵ + 2³ + 2² = 100101100₂.
Largest power 2⁸ → 9 digits; four powers → four 1s; 0s: 9 − 4 = 5.
5 − 4 = 1. Correct answer: A) 1.
Numbers given as powers
Problem
1) How many 0s are in the binary form of 2¹⁰ + 2⁴ + 1?
2) How many 1s are in the binary form of 2⁹ − 1?
Show solutionHide solution
Solution
2) 2⁹ − 1 = 511 = 111111111₂ — 9 ones.
An olympiad problem: counting ones
Problem
1) How many of the numbers from 0 to 255 (written with 8 bits) contain exactly three 1s? 2) How many 1s are there in all their binary forms together?
Show solutionHide solution
Solution
2) In every position exactly half of the 256 numbers have a 1: 128. For 8 positions: 8 · 128 = 1024. In general, the numbers 0…2ⁿ − 1 contain n · 2ⁿ⁻¹ ones in all.
This is where combinatorics meets number systems: every n-bit number is a choice of the positions that hold a 1.
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)Expected output
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.
Remember
- In a non-positional system (Roman numerals) a digit’s value does not depend on its place; in a positional system every place value is a power of the base.
- Base b uses the digits 0…b − 1; the expanded form N = aₖ·bᵏ + … + a₁·b + a₀ converts from any base to decimal.
- Decimal to binary: divide by 2 and read the remainders bottom to top; multiply the fractional part by 2 and read the whole parts top to bottom.
- The largest k-digit number is bᵏ − 1, the smallest is bᵏ⁻¹.
- The number of 1s in binary equals the number of different powers of two; the number of digits comes from 2ᵏ⁻¹ ≤ N < 2ᵏ; 0s = digits − 1s.