Number systems: positional systems and binary

Tell non-positional (Roman) and positional systems apart, write a number in expanded form, convert from any base to decimal and between decimal and binary, and count the 0s and 1s of a binary number.

  • Grades 7…9
  • 22 min
  • 12 questions
  • Lesson 14 of 59

In this lesson you will learn

  • Tell non-positional and positional systems apart; read and write Roman numerals
  • Write a number in expanded form and convert from any base to decimal
  • Convert decimal whole numbers and fractions to binary, and binary numbers to decimal
  • Find the number of digits, 0s and 1s in binary, and the largest and smallest k-digit numbers in a given base

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.

Simple explanation

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

Go from left to right and compare each symbol with the one on its right:
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

1) MMXXVI = 1000 + 1000 + 10 + 10 + 5 + 1 = 2026.
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.

Sign up free to keep reading

The rest of the lesson, the quiz and your notes open with an Educora account. Signing up takes a minute, and your progress is saved on all your devices.

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”.

Simple explanation

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², …

DecimalBase 5Binary
000
111
2210
3311
44100
510101
611110
712111
8131000
“10” is always the base itself: five in base 5, two in binary.
N = aₖ·bᵏ + aₖ₋₁·bᵏ⁻¹ + … + a₁·b + a₀

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

Multiply every digit by the place value of its position.
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.
Simple explanation
  1. 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.

  2. Write the place values

    The place values are powers of the base: 4⁰ = 1, 4¹ = 4, 4² = 16.

  3. Multiply and add

    3·16 + 2·4 + 1·1 = 48 + 8 + 1 = 57.

  4. Check

    Every digit must be smaller than the base: 3, 2, 1 < 4 ✓

Going deeper

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

1) 2 → 2·3 + 0 = 6 → 6·3 + 1 = 19 → 19·3 + 1 = 58 (the same answer as above).
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ᵏ⁻¹.

Nₘₐₓ = bᵏ − 1Nₘᵢₙ = 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

1) The largest digit is 4: 444₅ = 4·25 + 4·5 + 4 = 124 = 5³ − 1. The smallest: 100₅ = 25 = 5².
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.

n2ⁿn2ⁿ
01664
127128
248256
389512
416101024
532112048
Powers of two — the place values of binary
  1. Divide

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

  2. Repeat

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

  3. Read from bottom to top

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

  4. Check

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

Simple explanation

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.

N = b·q + r, 0 ≤ r ≤ b − 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

1) 77 ÷ 2 = 38, remainder 1
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

Loading simulation…
Tap the bits to build a number and see its decimal, octal and hexadecimal values. The “Divide by 2” mode shows the division method step by step.

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.

Simple explanation

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.375 · 2 = 0.75 → 0
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

1) 0.1011₂ = 1·½ + 0·¼ + 1·⅛ + 1·1/16 = 0.5 + 0.125 + 0.0625 = 0.6875.
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 ✓
Going deeper

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

3/8: 8 = 2³ → finite: 3/8 = ¼ + ⅛ = 0.011₂.
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.

2ⁿ = 100…0₂ (1 and n zeros)2ⁿ − 1 = 11…1₂ (n ones)

Where

n
the exponent

Number of 0s = number of digits − number of 1s. For example, 2⁹ − 1 = 511 = 111111111₂ — nine 1s.

2ᵏ⁻¹ ≤ N < 2ᵏ

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.

Going deeper

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

1) 2²⁹ = 536,870,912 ≤ 10⁹ < 1,073,741,824 = 2³⁰ ⇒ 30 digits. Another way: log₂10⁹ = 9 · log₂10 ≈ 9 · 3.32 ≈ 29.9 ⇒ [29.9] + 1 = 30.
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

Split 300 into powers of two: 300 − 256 = 44; 44 − 32 = 12; 12 − 8 = 4; 4 − 4 = 0.
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

1) 1 = 2⁰, so there are three different powers → three 1s; the largest power 2¹⁰ → 11 digits. 0s: 11 − 3 = 8 (10000010001₂).
2) 2⁹ − 1 = 511 = 111111111₂ — 9 ones.
Going deeper

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

1) Choose 3 of the 8 positions for the 1s: C(8, 3) = 8 · 7 · 6 / (1 · 2 · 3) = 56.
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”.

Python
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
300 = 100101100₂: four 1s, five 0s.

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.
Spotted a mistake or something inaccurate in this lesson?

Check yourself

12 questions. Every correct answer earns XP.

Question 1 / 12

Question 1 / 12. Which number system is non-positional?