py4kidsSearch
Exit slides Esc

Unit 1 — Computer Number Systems

Slide 1 of 65

  1. The problem: Three Friends, One Number?

    Three friends each wrote a number on a card, and each of them claims theirs is the biggest.

    Card Written by The number
    A Ana 101101₂
    B Ben 55₈
    C Cy 2D₁₆

    The small number after each one is its base. 101101₂ is written in base 2 (binary), 55₈ in base 8 (octal) and 2D₁₆ in base 16 (hexadecimal).

    Which card holds the biggest number?

    And one more puzzle for later: a web page paints a box in the colour #7FBF3F. Is that box mostly red, mostly green or mostly blue?

  2. No computer is needed for either puzzle, only pencil, paper and the ideas in this unit. By the end of Lesson 1 you will be able to answer both. Lessons 2 and 3 go further: converting any number into any base by hand, doing arithmetic in other bases, writing programs that convert for you, and reading numbers with a point, such as 0.101₂.

    • Elementary and above: read place value in bases 2, 8, 10 and 16, and convert between them by hand.

    • Elementary and above: count the 1s in a binary number, compare numbers in different bases, and add and subtract in another base.

    • Junior and above: convert base 10 to any base by repeated division, multiply by one digit, and find a mystery base.

    • Junior and above: write the conversions as Python loops, then use the int(text, base) shortcut.

    • Intermediate and above: convert fractions in bases 2, 8 and 16.

  5. Lesson 1 — Place value in bases 2, 8, 10 and 16

    Division: Elementary and above. This whole lesson is about pencil-and-paper work. It is everything the ACSL Elementary Computer Number Systems test asks, and it is the starting point for every other division.

  6. Place value in base 10

    You already know base 10. In the number 3,506, each digit has a place, and each place is worth 10 times the place to its right.

    Place value 1000 100 10 1
    Digit 3 5 0 6

    So 3506 means 3 × 1000 + 5 × 100 + 0 × 10 + 6 × 1. The place values are the powers of 10: 1, 10, 100, 1000, and so on. Base 10 uses ten digits, 0 to 9.

  7. Other bases work the same way

    In base b, each place is worth b times the place to its right, and the digits go from 0 up to b − 1.

    Base Name Digits Place values (right to left)
    2 binary 0 1 1, 2, 4, 8, 16, 32, 64, 128, 256, …
    8 octal 0 to 7 1, 8, 64, 512, 4096, …
    10 decimal 0 to 9 1, 10, 100, 1000, …
    16 hexadecimal ("hex") 0 to 9, then A B C D E F 1, 16, 256, 4096, 65536, …

    Hex needs sixteen digits, so after 9 it borrows letters: A = 10, B = 11, C = 12, D = 13, E = 14 and F = 15.

  8. To show which base a number is written in, ACSL writes the base as a small number after it: 101₂, 101₈, 101₁₀ and 101₁₆ are four different numbers. A number with no base written is in base 10.

    Computers store everything in binary, because a wire is either off (0) or on (1). Octal and hex are short ways for people to write long binary numbers, as you will see below.

  9. Any base to base 10: expanded notation

    To find the value of a number in base 10, multiply each digit by its place value and add. Write the place values above the digits first, starting with 1 on the right.

    Example 1. 101101₂

    Place value 32 16 8 4 2 1
    Digit 1 0 1 1 0 1

    101101₂ = 32 + 8 + 4 + 1 = 45. In binary every digit is 0 or 1, so you just add the place values that have a 1 under them.

    Example 2. 55₈ = 5 × 8 + 5 × 1 = 40 + 5 = 45.

  10. Example 3. 2D₁₆ = 2 × 16 + 13 × 1 = 32 + 13 = 45. (Remember that D means 13.)

    That solves the first puzzle: all three cards hold the same number, 45. Nobody wins; the friends just wrote 45 in three different bases.

    Watch out: the value of a digit is the digit times its place value. In 734₈ the 7 is worth 7 × 64 = 448, not 7 and not 700.

  11. Base 10 to base 2: take away powers of 2

    To write a base-10 number in binary, list the powers of 2 up to the number. Start at the biggest power that fits, take it away, and write 1 under it. Move right one place at a time: write 1 if that power fits into what is left (and take it away), or 0 if it does not.

    Example 4. Write 45 in binary.

    Power of 2 32 16 8 4 2 1
    Fits into what is left? 45 − 32 = 13 13 < 16, no 13 − 8 = 5 5 − 4 = 1 1 < 2, no 1 − 1 = 0
    Digit 1 0 1 1 0 1

    So 45 = 101101₂. Check it the other way: 32 + 8 + 4 + 1 = 45.

  12. Optional self-checker. If you can run a Python program, this one prints the binary form of a base-10 number, using exactly the "take away powers of 2" method above. Work each conversion by hand first, then use it to check yourself. It is saved as assets/l1.py; you do not need to understand the code yet.

  13. Try it
    n = int(input())
power = 1
while power * 2 <= n:
    power = power * 2
bits = ""
while power >= 1:
    if n >= power:
        bits = bits + "1"
        n = n - power
    else:
        bits = bits + "0"
    power = power // 2
print(bits)

  14. To run it, open a terminal in this unit's folder, type python assets/l1.py, then type a number such as 45 and press Enter; it prints 101101. You can also feed it a file: python assets/l1.py < assets/l1/1.in prints 1101, the binary form of 13.

  15. Counting the 1s

    A common Elementary question asks how many 1s are in the binary form of a number. Convert the number to binary, then count.

    Example 5. How many 1s are in the binary form of 45? 45 = 101101₂, which has 4 ones.

    Example 6. How many 1s are in the binary form of 64? 64 is itself a power of 2, so 64 = 1000000₂, which has just 1 one. Every power of 2 has exactly one 1 in binary.

  16. The grouping shortcut: 2 ↔ 8 ↔ 16

    Because 8 = 2 × 2 × 2, one octal digit is exactly three binary digits (bits). Because 16 = 2 × 2 × 2 × 2, one hex digit is exactly four bits.

    Octal digit Bits Hex digit Bits Hex digit Bits
    0 000 0 0000 8 1000
    1 001 1 0001 9 1001
    2 010 2 0010 A 1010
    3 011 3 0011 B 1011
    4 100 4 0100 C 1100
    5 101 5 0101 D 1101
    6 110 6 0110 E 1110
    7 111 7 0111 F 1111

    You do not need to memorize the table: each row is just the small number written with place values 4, 2, 1 (octal) or 8, 4, 2, 1 (hex).

  17. Binary to octal: split the bits into groups of 3, starting from the right, and add zeros on the left of the leftmost group if it is short. Replace each group by its octal digit.

    101101₂ → 101 101 → 55₈.

    Binary to hex: the same, with groups of 4 from the right.

    101101₂ → 0010 1101 → 2D₁₆.

    Octal or hex to binary: replace each digit by its 3 or 4 bits.

    3F₁₆ → 0011 1111 → 111111₂ (drop the zeros at the front).

  18. Octal to hex (or hex to octal): go through binary. Write the bits, then regroup them.

    Example 7. 173₈ → 001 111 011 → 1111011₂ → 0111 1011 → 7B₁₆.

    Watch out: always group from the right. Grouping 1111011 from the left as 1111 011 gives the wrong answer.

  19. Comparing numbers in different bases

    To compare numbers written in different bases, first write them all in the same base. Base 10 is usually easiest.

    Example 8. Which is larger, 1100100₂ or 145₈?

    1100100₂ = 64 + 32 + 4 = 100. 145₈ = 1 × 64 + 4 × 8 + 5 = 101. So 145₈ is larger, by 1.

    Do not compare the digits directly: 145₈ has fewer digits than 1100100₂, and it is still the larger number.

  20. Adding in another base

    Add column by column from the right, exactly as in base 10. The only change is when you carry: in base b, a column that reaches b or more carries 1 to the next column and keeps (sum − b).

    Example 9. 1011₂ + 110₂

      carries  1 1
           1 0 1 1
       +     1 1 0
       -----------
         1 0 0 0 1

  21. Right column: 1 + 0 = 1. Next: 1 + 1 = 2, which is 10₂: write 0, carry 1. Next: 0 + 1 + 1 (carry) = 2: write 0, carry 1. Next: 1 + 1 (carry) = 2: write 0, carry 1, and the carry becomes a new leftmost 1. Answer: 10001₂. Check in base 10: 11 + 6 = 17 = 16 + 1 = 10001₂.

    Example 10. 57₈ + 26₈

  22. Right column: 7 + 6 = 13, which is 8 + 5: write 5, carry 1. Next: 5 + 2 + 1 = 8, which is 8 + 0: write 0, carry 1. Answer: 105₈. Check: 47 + 22 = 69 = 64 + 0 + 5 = 105₈.

    Example 11. 9C₁₆ + 2B₁₆

    Right: C + B = 12 + 11 = 23 = 16 + 7: write 7, carry 1. Next: 9 + 2 + 1 = 12, which is the digit C. Answer: C7₁₆.

  23. Subtracting in another base

    Subtract column by column from the right. When the top digit is too small, borrow 1 from the next column; in base b the borrowed 1 is worth b, not 10.

    Example 12. 52₈ − 17₈

    Right column: 2 − 7 does not work, so borrow: 2 + 8 = 10, and 10 − 7 = 3. Next: the 5 lent 1 and is now 4, and 4 − 1 = 3. Answer: 33₈. Check: 42 − 15 = 27 = 3 × 8 + 3.

  24. Example 13. 100₂ − 1₂

    The right column is 0 − 1, and the next column is also 0, so borrow from the 1 at the far left. It lends 2 to the middle column; the middle lends 2 to the right column and keeps 1. Right: 2 − 1 = 1. Middle: 1 − 0 = 1. Left: 0. Answer: 11₂ (4 − 1 = 3).

  25. Hex colours

    A screen makes every colour by mixing red, green and blue light. Each of the three amounts goes from 0 (none) to 255 (full), and 255 = FF₁₆, so each amount fits in exactly two hex digits. A web colour is written #RRGGBB: two hex digits of red, two of green, then two of blue.

    Colour code Red Green Blue Colour
    #FF0000 255 0 0 pure red
    #00FF00 0 255 0 pure green
    #0000FF 0 0 255 pure blue
    #FFFFFF 255 255 255 white (all light)
    #000000 0 0 0 black (no light)
    #FFFF00 255 255 0 yellow (red + green light)

  26. Example 14. Back to the second puzzle: #7FBF3F. Red is 7F₁₆ = 7 × 16 + 15 = 127. Green is BF₁₆ = 11 × 16 + 15 = 191. Blue is 3F₁₆ = 3 × 16 + 15 = 63. Green is the largest amount, so the box is mostly green: a fresh leaf green.

    Since there are 256 choices for each of the three amounts, there are 256 × 256 × 256 = 16,777,216 colour codes in all.

    Elementary checklist. You can now:

    • find the base-10 value of a number in base 2, 8 or 16 by expanded notation;

    • write a base-10 number in binary, and count its 1s;

    • convert between bases 2, 8 and 16 by grouping bits;

    • compare numbers written in different bases;

    • add and subtract in bases 2, 8 and 16;

    • read the red, green and blue amounts of a hex colour.

  28. That is the whole Elementary test. Exercises 1 to 9 are an Elementary practice test. Junior, Intermediate and Senior students continue with Lessons 2 and 3.

  29. Lesson 2 — Any base, by hand and by program

    Division: Junior and above.

  30. Base 10 to any base: repeated division

    Taking away powers works, but for big numbers and bases other than 2 there is a faster method: divide by the base again and again.

    1. Divide the number by the base. Write down the remainder.

    2. Replace the number by the quotient (the whole-number answer).

    3. Repeat until the quotient is 0.

    4. Read the remainders from the last one to the first: that is the number in the new base.

    Example 1. Write 45 in base 8.

    Divide Quotient Remainder
    45 ÷ 8 5 5
    5 ÷ 8 0 5

  31. Reading the remainders from the bottom up gives 55₈, as in the hook.

    Example 2. Write 2023 in base 16.

    Divide Quotient Remainder
    2023 ÷ 16 126 7
    126 ÷ 16 7 14 = E
    7 ÷ 16 0 7

    Bottom up: 7E7₁₆. Check: 7 × 256 + 14 × 16 + 7 = 1792 + 224 + 7 = 2023.

  32. Why it works: the first remainder is what is left over after taking out every whole group of the base, so it is the ones digit. Dividing by the base shifts every other digit one place to the right, so the next remainder is the next digit, and so on.

  33. The method works for any base, not only 2, 8 and 16. Example 3. 100 in base 5: 100 ÷ 5 = 20 r 0; 20 ÷ 5 = 4 r 0; 4 ÷ 5 = 0 r 4. Bottom up: 400₅, and indeed 4 × 25 = 100.

  34. Larger conversions

    Choose the easiest path.

    • Between 2, 8 and 16: group bits (Lesson 1). Never go through base 10; it is slower and easier to get wrong.

    • Between base 10 and anything: expanded notation one way, repeated division the other way.

    • Between two other bases, such as 5 and 7: go through base 10.

    Example 4. Convert 7A3₁₆ to octal. 7A3₁₆ → 0111 1010 0011 → 011 110 100 011 → 3643₈. (Regroup the 12 bits in threes from the right.)

  35. Example 5. Convert 213₄ to base 6. 213₄ = 2 × 16 + 1 × 4 + 3 = 39. 39 ÷ 6 = 6 r 3; 6 ÷ 6 = 1 r 0; 1 ÷ 6 = 0 r 1, so the answer is 103₆.

  36. A mystery base

    Sometimes the base is the unknown. Expanded notation still works: write the place values with the letter b.

    Example 6. In what base b is the number 21, written in base b, equal to 13? 21 in base b is 2 × b + 1, so 2b + 1 = 13 and b = 6. Check: 21₆ = 12 + 1 = 13.

  37. If the equation is harder, try bases one at a time. The base must be bigger than every digit of the number, which tells you where to start.

  38. Multiplying by one digit

    ACSL may ask you to multiply a number by a single digit in another base (it never asks you to divide). Work from the right, as in base 10: multiply each digit, add the carry, then write down the ones digit in that base and carry the rest.

    Example 7. 247₈ × 5₈

    • 7 × 5 = 35 = 4 × 8 + 3: write 3, carry 4.

    • 4 × 5 + 4 = 24 = 3 × 8 + 0: write 0, carry 3.

    • 2 × 5 + 3 = 13 = 1 × 8 + 5: write 5, carry 1.

    • The last carry 1 becomes the leftmost digit.

    Answer: 1503₈. Check in base 10: 247₈ = 167, and 167 × 5 = 835 = 512 + 5 × 64 + 0 × 8 + 3 = 1503₈.

    Example 8. 3A₁₆ × 4₁₆: A × 4 = 40 = 2 × 16 + 8: write 8, carry 2; 3 × 4 + 2 = 14 = E. Answer: E8₁₆.

  40. Hex colours at Junior level

    Junior questions do arithmetic on colour codes, one channel (two hex digits) at a time.

    Example 9. The inverse of a colour replaces each amount by 255 minus it; on screen it looks like a photo negative. Since 255 = FF₁₆, subtract each channel from FF. The inverse of #7FBF3F is FF − 7F = 80, FF − BF = 40, FF − 3F = C0, so it is #8040C0, a purple.

    Subtracting from FF never needs a borrow: each hex digit d just becomes F − d.

  41. Example 10. A grey has the same amount of red, green and blue. Which grey is exactly halfway between black #000000 and white #FFFFFF? Half of 255 is 127 when you round down, and 127 = 7F₁₆, so the answer is #7F7F7F.

  42. Repeated division as a program

    Here is repeated division in Python. % gives the remainder and // the quotient, exactly the two numbers in each row of the table. The string DIGITS holds the sixteen digit symbols, so DIGITS[r] is the symbol for the remainder r: DIGITS[14] is "E". Each new digit goes on the front of the text, because the remainders come out from right to left.

  43. DIGITS = "0123456789ABCDEF"
n = 2023
base = 16
text = ""
while n > 0:
    remainder = n % base
    text = DIGITS[remainder] + text
    n = n // base
print(text)

    Output

    7E7

  44. text = DIGITS[remainder] + text builds the answer backwards, which is the same as reading the remainders from the bottom up. Try it with other values of n and base, such as 45 in base 2 and 100 in base 5.

    One edge case: if n starts at 0, the loop never runs and text stays empty. A contest program must print 0, so it handles 0 first.

  45. DIGITS = "0123456789ABCDEF"
n = 0
base = 2
text = ""
if n == 0:
    text = "0"
while n > 0:
    text = DIGITS[n % base] + text
    n = n // base
print(text)

    Output

    0

  46. Put it together: this program reads the red, green and blue amounts of a colour, in base 10, and prints its colour code. Each amount becomes exactly two hex digits: the first is amount // 16 and the second amount % 16. That is repeated division stopped after two steps, so an amount under 16, such as 9, still gets its leading zero: 09. It is saved as assets/l2.py.

  47. Try it
    DIGITS = "0123456789ABCDEF"
parts = input().split()
code = "#"
for part in parts:
    amount = int(part)
    code = code + DIGITS[amount // 16] + DIGITS[amount % 16]
print(code)

  48. Run it from this unit's folder:

    python assets/l2.py < assets/l2/2.in

    The input 127 191 63 prints #7FBF3F, the hook's colour. assets/l2/4.in holds 16 9 170, which checks the leading zero: #1009AA.

  49. Lesson 3 — Converting programs, and fractions in other bases

    Division: Junior and above.

  50. Any base to base 10 as a program

    Expanded notation multiplies each digit by its place value. A program uses a neater way to get the same total: read the digits from left to right, and for each one, multiply the value so far by the base and add the digit.

  51. For 2D₁₆: start at 0; the digit 2 gives 0 × 16 + 2 = 2; the digit D gives 2 × 16 + 13 = 45. Each multiplication by the base moves the earlier digits one place to the left, so every digit ends up multiplied by its place value.

    To get a digit's value from its symbol, the function digit_value walks through DIGITS until it finds the symbol.

  52. DIGITS = "0123456789ABCDEF"


def digit_value(symbol):
    for value in range(16):
        if DIGITS[value] == symbol:
            return value
    return -1


def to_decimal(text, base):
    total = 0
    for symbol in text:
        total = total * base + digit_value(symbol)
    return total


print(to_decimal("2D", 16))
print(to_decimal("101101", 2))
print(to_decimal("55", 8))

    Output

    45
45
45

  53. All three lines print 45, the hook's answer, computed three ways. digit_value returns -1 for a symbol that is not a digit, so a typo shows up as a strange total rather than a crash.

    The other direction is repeated division from Lesson 2, as a function:

    DIGITS = "0123456789ABCDEF"


def to_base(n, base):
    if n == 0:
        return "0"
    text = ""
    while n > 0:
        text = DIGITS[n % base] + text
        n = n // base
    return text


print(to_base(45, 2))
print(to_base(2023, 16))
print(to_base(0, 8))

    Output

    101101
7E7
0

  54. The shortcut int(text, base)

    You already know int("45"), which turns text into a number. int can also take a second value: the base the text is written in. It does exactly what to_decimal does.

  55. print(int("2D", 16))
print(int("101101", 2))
print(int("55", 8))
print(int("1313", 7))

    Output

    45
45
45
500

  56. int(text, base) works for any base from 2 to 36, and it expects the text to use only digits of that base: int("19", 8) is an error, because 9 is not an octal digit. Use it in your programs now that you know how it works by hand. Python has no shortcut in the other direction that this book uses, so to go from base 10 you still write to_base yourself. On the short-answer part of the contest there is no computer at all: the hand methods are what count there.

  57. Put it together: this program reads a number, the base it is written in, and a new base, all on one line, and prints the number in the new base. It goes through base 10: int(text, base) in, to_base out. It is saved as assets/l3.py.

  58. Try it
    DIGITS = "0123456789ABCDEF"


def to_base(n, base):
    if n == 0:
        return "0"
    text = ""
    while n > 0:
        text = DIGITS[n % base] + text
        n = n // base
    return text


parts = input().split()
value = int(parts[0], int(parts[1]))
print(to_base(value, int(parts[2])))

  59. Run it from this unit's folder:

    python assets/l3.py < assets/l3/1.in

    The input 1777 8 16 prints 3FF. Test the edges too: assets/l3/2.in converts 0 (it must print 0, not an empty line), and assets/l3/5.in converts 101101 2 8 to 55.

  60. Fractions in other bases

    Division: Intermediate and above.

    In base 10, the places to the right of the point are worth 1/10, 1/100, 1/1000, and so on: each place is worth the place on its left divided by 10. Other bases work the same way, dividing by the base.

    Base Place values after the point
    2 1/2, 1/4, 1/8, 1/16, …
    8 1/8, 1/64, 1/512, …
    16 1/16, 1/256, 1/4096, …

    Base to fraction: use expanded notation, then add the fractions over the smallest place's denominator.

    Example 1. 0.101₂ = 1/2 + 0/4 + 1/8 = 4/8 + 1/8 = 5/8.

  61. Example 2. 0.24₈ = 2/8 + 4/64 = 16/64 + 4/64 = 20/64 = 5/16 (in lowest terms).

    Example 3. 0.4C₁₆ = 4/16 + 12/256 = 64/256 + 12/256 = 76/256 = 19/64.

    Example 4. 11.01₂ has a whole part and a fraction part: 11₂ = 3, and 0.01₂ = 1/4, so 11.01₂ = 3 1/4 = 13/4.

    Fraction to base: rewrite the fraction with a denominator that is a place value (for base 2: 2, 4, 8, 16, …), then split the top into place values.

  62. Example 5. Write 3/8 in base 2. 3/8 = 2/8 + 1/8 = 1/4 + 1/8. The places are 1/2 (0), 1/4 (1) and 1/8 (1), so 3/8 = 0.011₂.

    Example 6. Write 3/4 in base 16. 3/4 = 12/16, and 12 is the digit C, so 3/4 = 0.C₁₆.

    The grouping shortcut still works, starting from the point and grouping to the right, adding zeros at the end of the last group if it is short. 0.011₂ → 0.011 → 0.3₈, and 0.1011₂ → 0.1011 → 0.B₁₆.

  63. Watch out: in 0.101₂ the first 1 is worth 1/2, not 1/10.

    • Elementary and above: each place is worth a power of the base, so 101101₂, 55₈ and 2D₁₆ are all 45.

    • Elementary and above: group binary digits in 3s for base 8 and in 4s for base 16.

    • Elementary and above: when you add or subtract in base b, carry or borrow b, not 10.

    • Junior and above: repeated division by the base gives the digits from last to first, and int(text, base) converts back to base 10.

    • Intermediate and above: the places after the point are worth 1/2, 1/4, 1/8, …, so 0.101₂ = 5/8.

    You can now move a number between bases by hand, and check your work with a program.