Binary

Mix.install([
  {:kino, github: "livebook-dev/kino", override: true},
  {:kino_lab, "~> 0.1.0-dev", github: "jonatanklosko/kino_lab"},
  {:vega_lite, "~> 0.1.4"},
  {:kino_vega_lite, "~> 0.1.1"},
  {:benchee, "~> 0.1"},
  {:ecto, "~> 3.7"},
  {:math, "~> 0.7.0"},
  {:faker, "~> 0.17.0"},
  {:utils, path: "#{__DIR__}/../utils"}
])

Navigation

Return Home Report An Issue

Setup

Ensure you type the ea keyboard shortcut to evaluate all Elixir cells before starting. Alternatively you can evaluate the Elixir cells as you read.

Binary

TODO - THIS LESSON IS A WIP

Under the hood, computers store information as electrical signals, either on or off, 0 or 1. So you might wonder, how are they able to represent numbers larger than 1?

Fortunately, humans have been thinking about base 2 counting systems since the days of ancient Egypt. The current binary counting system was created by Gottfried Wilhelm Leibniz In the 17th Century.

What’s a base 2 counting system? Well first, let’s take a second to appreciate that we have a base 10 counting system. We have ten digits, and use placeholders to represent shifting values.

1 2 3 4 5 6 7 8 9 0

Early computers were built to perform mathematical calculations. Therefore it’s necessary to be able to represent an entire number system. We use Integers to represent whole positive or negative numbers. 100 is an integer, 0 is an integer, and so is -10.

Take the example number 4762. It has

• 4 thousands
• 7 hundreds
• 6 tens
• 2 ones

flowchart
  Thousands --- 4
  Hundreds --- 7
  Tens --- 6
  Ones --- 2

Counting Visualization

To help you visualize counting in a base10 system, Here’s a visualization of 4 placeholders. You have your ones, tens, hundreds, and thousands.

Evaluate the Elixir cell below to visualize how numbers shift to the left placeholder as you count.

## TODO - Hide

Kino.animate(500, 0, fn i ->
  digits = Integer.digits(i)
  reverse_digits = Enum.reverse(digits)
  ones = Enum.at(reverse_digits, 0)
  tens = Enum.at(reverse_digits, 1)
  hundreds = Enum.at(reverse_digits, 2)
  thousands = Enum.at(reverse_digits, 3)
  md = Kino.Markdown.new("
  ```mermaid
  flowchart
  Thousands --- TH[#{thousands || 0}]
  Hundreds --- H[#{hundreds || 0}]
  Tens --- T[#{tens || 0}]
  Ones --- O[#{ones || 0}]
```
")

  # performant_alternative = [thousands || 0, hundreds || 0, tens || 0, ones]

  {:cont, md, rem(i + 1, 9999)}
end)

Now, a base 2 counting system works on the same principle as a base 10, except we only have 2 digits to represent numbers with.

0 1

Every time we run out of digits, we shift the placeholder over.

Take the example binary number 1011 which is eleven in base10. It has

• 1 eight
• 0 four
• 1 two
• 1 one

It’s eleven, because 8 + 2 + 1 = 11.

You can see how our base10 numbers are represented as binary in this table.

# TODO - Hide

data =
  Enum.map(1..500, fn integer ->
    binary = Integer.digits(integer, 2) |> Enum.join() |> String.to_integer()
    %{base10: integer, base2: binary}
  end)

Kino.DataTable.new(data)

Counting Binary Visualization

Want to see binary counting in action? Evaluate the Elixir cell below to see an animation.

# Todo - Hide

Kino.animate(1000, 0, fn i ->
  digits = Integer.digits(i, 2)
  reverse_digits = Enum.reverse(digits)
  ones = Enum.at(reverse_digits, 0)
  twos = Enum.at(reverse_digits, 1)
  fours = Enum.at(reverse_digits, 2)
  eights = Enum.at(reverse_digits, 3)
  sixteens = Enum.at(reverse_digits, 4)
  thirtytwos = Enum.at(reverse_digits, 5)
  sixtyfours = Enum.at(reverse_digits, 6)
  hundredtwentyeights = Enum.at(reverse_digits, 7)

  md = Kino.Markdown.new("
  ```mermaid
  flowchart
  Integer[#{i}]
  HundredAndTwentyEights --- 128[#{hundredtwentyeights || 0}]
  SixtyFours --- 64[#{sixtyfours || 0}]
  ThirtyTwos --- 32[#{thirtytwos || 0}]
  Sixteens --- 16[#{sixteens || 0}]
  Eights --- 8[#{eights || 0}]
  Fours --- 4[#{fours || 0}]
  Twos --- 2[#{twos || 0}]
  Ones --- 1[#{ones || 0}]
```
")

  # performant_alternative = ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0] -- Enum.map(0..length(digits), fn _ -> 0 end)) ++ digits
  max = 128 + 64 + 32 + 16 + 4 + 2 + 1
  {:cont, md, rem(i + 1, max)}
end)

This is how despite only having on and off, 0 and 1 computers are able to represent large numbers.

You’ll notice that in the above animation we show eight placeholders. That’s because binary digits are grouped together in eights. each digit is called a bit, and each grouping of eight is called a byte.

As we count from 1 to 9, we then add a 1 in the placeholder on the left, and restart at 0. You probably do this intuitively. This means we have placeholders for ones, tens, hundreds, etc.

The base10 counting system shouldn’t be taken for granted. Humans have been intellectually capable of creating a base10 counting system for over 200000 years, and yet our current system was only invented in the 7th century. 🤯

Can you imagine if we had different symbols for every number? It would be impossible to remember.

CodePoints

How Did We Go From Integers to Strings?

You might wonder how we went from representing integers to representing strings and any valid text character.

Essentially, characters have an equivalent integer associated with them. This integer is called a code point.

For example, the code point for the letter a is 97. Lowercase and uppercase letters have different codepoints.

You can find the code point of any character by using ? in Elixir. Evaluate the Elixir cell below to see how ?a returns 97.

?a

Once again, while it’s useful to be aware of how strings are represented by the computer. it’s not crucial to understand for most purposes.

If you are curious, the full list of representable characters is called the The Unicode Standard. below is a table of code points for uppercase and lowercase letters in the alphabet.

You do not need to memorize these values! The goal of this lesson is simply awareness.

# TODO - hide

"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
|> String.codepoints()
|> Enum.map(fn char ->
  <> = char
  %{character: char, code_point: code_point}
end)
|> Kino.DataTable.new()

In the Elixir cell below, enter the codepoint for the letter "Y". You’re allowed to use ?!

Commit Your Progress

Run the following in your command line from the project folder to track and save your progress in a Git commit.

$ git add .
$ git commit -m "finish deprecated binary section"