In [1]:
from notebook.services.config import ConfigManager
from IPython.paths import locate_profile
cm = ConfigManager(profile_dir=locate_profile(get_ipython().profile))
cm.update('livereveal', {
              'theme': 'solarized',
              'transition': 'zoom',
              'start_slideshow_at': 'selected',
})


Out[1]:
{'start_slideshow_at': 'selected', 'theme': 'solarized', 'transition': 'zoom'}

Math, Representation and Binary Arithmetic

Dr. Chris Gwilliams

gwilliamsc@cardiff.ac.uk

Contents

  • Mathematic Operations
  • Binary Conversion
  • Boolean Logic
  • Binary Arithmetic

Operations

We have covered (+, -, / and *), but there are more built in.

  • **: To the power of
  • % : Modulo

What is Modulo?

a % b The remainder after a is divided by b

Exercise

Given three integers, write them in the order such that a % b = c or a ** b = c

  • 13 3 5
  • 2 144 12
  • 67 12 146
  • 2 8.5 19
BONUS MYSTERY QUESTION

Reorder and/or use the symbols to get an answer of 64

  • 4 11 3 = 64

In [27]:
13 % 5 == 3
12 ** 2 == 144
146 % 67 == 12
19 % 8.5 == 2

4 ** (3 % 11)


Out[27]:
64

Binary

A way of representing data using an ON or OFF flag using a 1 or a 0.

Why does it exist?

Because it the simplest method of storing information. A trivial yes or no can be stored, as well as whole novels (or programs, as you will be writing)

How, you ask?

A single digit of binary is 0 or 1. In a computer, this takes up 1 bit of memory.

8 bits = 1 byte

1 byte is the smallest addressable unit of memory

Because 8 bits is 1 byte, then all units beyond that are multipls of 8.

1024 byte = 1 kilobyte 1024 kilobytes = 1 ??


In [ ]:
1024 `megabytes` = 1 `??`

In [ ]:
1024 `gigabyte` = 1 `??`

In [ ]:
1024 `terabyte` = 1 `??`

1024 byte = 1 kilobyte

1024 kilobytes = 1 megabyte

1024 megabytes = 1 gigabyte

1024 gigabytes = 1 terabyte

1024 terabytes = 1 petabyte

1024 petabytes = 1 exabyte

1024 exabytes = 1 zettabyte

1024 zettabytes = 1 yotabyte

So, what about these hard drive manufacturers here? They are not alone, many follow this standard!

So, when you buy a laptop and they say it has a 3000GB hard drive (or 3TB), this may not be the case!

Exercise

How fast is your internet? Speed test it now or test the 4G on your phone.

How many mega bytes per second?

MB vs Mb

1 Megabit (Mb) is NOT equal to 1 Megabyte (MB)!

1 megabit = 1,000,000bits = 1/8 of a megabyte

Exercise

If I have a 3TB hard drive, how many 650 MB video files can I store on it?


In [26]:
movies_per_gb = 1024.0/650.0
print(movies_per_gb) #number of videos I can store in 1GB
movies_per_tb = float(movies_per_gb * 1024)
print(movies_per_tb) 
print(movies_per_tb * 3) #movies I can fit on my 3TB drive

print(((1024.0/650.0) * 1024.0) * 3.0)


1.57538461538
1613.19384615
4839.58153846
4839.58153846

Binary

Everything we store (movies, text, programs), all come down to binary in their storage format. Before we get to this, we first need to know how convert numbers to binary and understand each bit.

What is the denary equivalent of this number? 0 0 0 1 0 1


In [ ]:
32 16 8 4 2 1
--------------
0  0  0 1 0 1

Denary to Binary and Binary to Denary

Using the method in the slide above, we can convert by doing the following things:

  1. Check the number of bits. 4 bit binary has 4 digits (0000), so we have a maximum of 15 numbers we can represent
  2. Draw a table like the one in the previous slide for the number of bits
  3. Check if the number you want to convert fits in to the left most bit:
    • If it does: add a 1 and subtract the number represented by the bit from the number you want to convert
    • If it does not: add a 0
  4. Move along to the next bit and repeat step 3 until you get to the right most bit

Example

Convert 27 to binary.

  1. 5 bit binary can represent numbers up to 31, so we know our binary number has 5 bits.

    16 8 4 2 1

  2. Start at 16, does 16 go into 27?


In [28]:
Yes. 
 16  8  4  2  1
 --------------
 1
Move to next bit. NUMBER = 27 - 16 = 11
Does 8 go into 11?


  File "<ipython-input-28-ef7911a2cfe4>", line 1
    Yes.
         ^
SyntaxError: invalid syntax

In [ ]:
Yes.
16  8  4  2  1
--------------
1  1
Move to next bit. NUMBER = 9 - 8 = 1
Does 3 go into 4?

In [ ]:
No.
16  8  4  2  1
--------------
1   1  0
Move to next bit. NUMBER still equals 1
Does 3 go into 2?

In [ ]:
Yes.
16  8  4  2  1
--------------
1   1  0  1
Move to next bit. NUMBER still equals 1
Does 1 go into 1?

In [ ]:
Yes.
16  8  4  2  1
--------------
1   1  0  1  1
Move to next bit. NUMBER = 1 - 1 = 0.
We are at the right most bit.

So, the binary representation for 27 is:
11011

Exercise

Find the 8 bit binary representation:

  • 127
  • 2
  • 64
  • 79
  • 34

Reverse engineer the approach to find the decimal representation of:

  • 11101111
  • 00011110
  • 11110001
  • 10101010
  • 01010101

In [ ]:
128  64  32  16  8  4  2  1
---------------------------
0    1   1   1   1  1  1  1  (127)
0    0   0   0   0  0  1  0 (2)
0    1   0   0   0  0  0  0 (64)
0    1   0   0   1  1  1  1 (79)
0    1   1   0   0  0  1  0 (34)

---

128  64  32  16  8  4  2  1
---------------------------
1    1   1   0   1  1  1  1 (239)
0    0   0   1   1  1  1  0 (30)
1    1   1   1   0  0  0  1 (241)
1    0   1   0   1  0  1  0 (170)
0    1   0   1   0  1  0  1 (85)

Bakuro

Ever played Kakuro or Sudoku? Well, Bakoru is a modification thought up by the people behind Computing At School. The aim is to fill in the blanks so they amount to the row and/or column total.

A grid (of any size) where numbers on each row must add up to the total at the stop blocks (rows with a total written in them and marked by a diagonal separator. Columns must also add up to the total in the stop block. A stop block would typically look like this:

Let's try to play Kakuro first.

https://gitlab.cs.cf.ac.uk/scm7cg/bakuro-gen

+---------------+-----------------+---------------+---------------+----------------+ | 12 | 4 | 7 | 13 | Col: | Row: 36 | +---------------+-----------------+---------------+---------------+----------------+ | 4 | 2 | 1 | 4 | Col: | Row: 11 | +---------------+-----------------+---------------+---------------+----------------+ | 11 | Col: 6| Row: 11 | 9 | 14 | Col: | Row: 23 | +---------------+-----------------+---------------+---------------+----------------+ | 2 | 4 | 6 | 11 | Col: | Row: 23 | +---------------+-----------------+---------------+---------------+----------------+ | Col: 29| Row: | Col: 4| Row: | Col: 23| Row: | Col: 42| Row: | | +---------------+-----------------+---------------+---------------+----------------+
---------------+-----------------+---------------+---------------+----------------+ | 0b1100/12 | 0b100 /4 | 0b111 /7 | 0b1101 /13 | Col: | Row: 36 | +---------------+-----------------+---------------+---------------+----------------+ | 0b100/4 | 0b10 /2 | 0b1 /1 | 0b100 /4 | Col: | Row: 11 | +---------------+-----------------+---------------+---------------+----------------+ | 0b1011 / 11 | Col: 6| Row: 11 | 0b1001 /9 | 0b1110 /14 | Col: | Row: 23 | +---------------+-----------------+---------------+---------------+----------------+ | 0b10 /2 | 0b100 /4 | 0b110 /6 | 0b1011 /11 | Col: | Row: 23 | +---------------+-----------------+---------------+---------------+----------------+ | Col: 29| Row: | Col: 4| Row: | Col: 23| Row: | Col: 42| Row: | | +---------------+-----------------+---------------+---------------+----------------+

Exercise

Using the grid above, change the decimal numbers to binary

Generate bakuro grid live!

Representing Text

So, we can store numbers in binary. How do we store letters?

Why can we not just give a number to every letter in the alphabet?

How would we represent upper case? How would we handle symbols? What about other alphabets?

    _    ____   ____ ___ ___ _
   / \  / ___| / ___|_ _|_ _| |
  / _ \ \___ \| |    | | | || |
 / ___ \ ___) | |___ | | | ||_|
/_/   \_\____/ \____|___|___(_)

The American Standard Code for Information Exchange. All characters are stored as codes and can be found through a lookup table.

NOTE: Character encoding is covered the Software Development Skills 2 course in the next semester.

Exercise

Convert the following binary values to decimal. Then use the look up table to find the char values and create words. Rearrange to form a sentence:

01100111 01101001 01110110 01100101

01101110 01100101 01110110 01100101 01110010

01110101 01110000

01100111 01101111 01101110 01101110 01100001

01111001 01101111 01110101