Representing Numbers in Binary

4.13. Representing Numbers in Binary#

4.13.1. Decimal (base 10)#

When dealing with number day-to-day we use the decimal system. This uses the digits 0-9. How does this work?

Let’s take the number 34 078 as an example and fill it into the table below.

\(10^4\)
\(10 000\)
\(10^3\)
\(1000\)
\(10^2\)
\(100\)
\(10^1\)
\(10\)
\(10^0\)
\(1\)

3

4

0

7

8

The way we interpret the number 34 078 is that it is

\((\mathbf{3} \times 10^4) + (\mathbf{4} \times 10^3) + (\mathbf{0} \times 10^2) + (\mathbf{7} \times 10^1) + (\mathbf{8} \times 10^0) = \mathbf{34\,078}\)

or alternatively

\((\mathbf{3} \times 10\,000) + (\mathbf{4} \times 1\,000) + (\mathbf{0} \times 100) + (\mathbf{7} \times 10) + (\mathbf{8} \times 1) = \mathbf{34\,078}\)

4.13.2. Binary (base 2)#

When computers store information they do so using the binary system. Information is transferred using binary digits, or bits. Typically we think of computer storage in terms of bytes, where a byte is equal to 8 bits.

Bits are mainly represented using digits 1 and 0, which can also represent values such as True/False and On/Off.

The binary system differs from the decimal system in that it operates in based 2 rather than base 10.

Binary to Decimal#

Example

Let’s take the number 10101 as an example and fill it into the table below.

\(2^4\)
\(16\)
\(2^3\)
\(8\)
\(2^2\)
\(4\)
\(2^1\)
\(2\)
\(2^0\)
\(1\)

1

0

1

0

1

The way we interpret the binary number 10101 is

\((\mathbf{1} \times 2^4) + (\mathbf{0} \times 2^3) + (\mathbf{1} \times 2^2) + (\mathbf{0} \times 2^1) + (\mathbf{1} \times 2^0) = \mathbf{21}\)

or alternatively

\(\mathbf{1} \times 16) + (\mathbf{0} \times 8) + (\mathbf{1} \times 4) + (\mathbf{0} \times 2) + (\mathbf{1} \times 1) = \mathbf{21}\)

Example

We can store much larger numbers by going to higher powers of 2.

Let’s take the number 10011101, and again fill it out in a table.

\(2^7\)
\(128\)
\(2^6\)
\(64\)
\(2^5\)
\(32\)
\(2^4\)
\(16\)
\(2^3\)
\(8\)
\(2^2\)
\(4\)
\(2^1\)
\(2\)
\(2^0\)
\(1\)

1

0

0

1

1

1

0

1

The way we interpret the binary number 10011101 is

\((\mathbf{1} \times 2^7) + (\mathbf{0} \times 2^6) + (\mathbf{0} \times 2^5) + (\mathbf{1} \times 2^4) + (\mathbf{1} \times 2^3) + (\mathbf{1} \times 2^2) + (\mathbf{0} \times 2^1) + (\mathbf{1} \times 2^0) = \mathbf{157}\)

or alternatively

\((\mathbf{1} \times 128) + (\mathbf{0} \times 64) + (\mathbf{0} \times 32) + (\mathbf{1} \times 16) + (\mathbf{1} \times 8) + (\mathbf{1} \times 4) + (\mathbf{0} \times 2) + (\mathbf{1} \times 1) = \mathbf{157}\)

Decimal to Binary#

Converting from the decimal system is a bit more challenging. Below is the algorithm used to convert a decimal number \(n\) to its binary representation.

Let n be a decimal integer

Find x where x is the largest value for which 2^x <= n

Let b represent the binary representation of n

For i = x, ..., 0

     If 2^x <= n>

         Next digit in b is 1

         Update n to be n - 2^x

     Else

         Next digit in b is 0

Example

Suppose \(n = \textcolor{blue}{21}\). The highest value of \(x\) for which \(2^x <= 21\) is \(x = 4\). \(2^4 = 16\). \(16 <= 21\).

Next we’ll iterate through values \(x = 4, 3, 2, 1, 0\).

\(2^4 = \textcolor{red}{16}\). \(16 <= \textcolor{blue}{21}\) is True, so the next digit in \(b\) is 1 and update \(n\) to be \(\textcolor{blue}{21} - \textcolor{red}{16} = \textcolor{blue}{5}\).

\(2^3 = \textcolor{red}{8}\). \(8 <= \textcolor{blue}{5}\) is False, so the next digit in \(b\) is 0.

\(2^2 = \textcolor{red}{4}\). \(4 <=\textcolor{blue}{5}\) is True, so the next digit in \(b\) is 1 and update \(n\) to be \(\textcolor{blue}{5} - \textcolor{red}{4} = \textcolor{blue}{1}\).

\(2^1 = \textcolor{red}{2}\). \(2 <= \textcolor{blue}{1}\) is False, so the next digit in \(b\) is 0.

\(2^0 = \textcolor{red}{1}\). \(1 <= \textcolor{blue}{1}\) is True, so the next digit in $b$ is 1 and update \(n\) to be \(\textcolor{blue}{1} - \textcolor{red}{1} = \textcolor{blue}{0}\).

Hence the binary representation of 21 is 10101. Another way to think about it is that you want to put 1’s and 0’s in the empty boxes such that if there is a 1 in the box, you add the values in the boxes above to get to 21.

\(2^4\)
\(16\)
\(2^3\)
\(8\)
\(2^2\)
\(4\)
\(2^1\)
\(2\)
\(2^0\)
\(1\)

i.e.

\(2^4\)
\(16\)
\(2^3\)
\(8\)
\(2^2\)
\(4\)
\(2^1\)
\(2\)
\(2^0\)
\(1\)

1

0

1

0

1

Example

Suppose \(n = \textcolor{blue}{157}\). The highest value of \(x\) for which \(2^x <= 157\) is \(x = 7\). \(2^7 = 128\). \(128 <= 157\).

Next we’ll iterate through values \(x = 7, 6, 5, 4, 3, 2, 1, 0\).

\(2^7 = \textcolor{red}{128}\). \(128 <= \textcolor{blue}{157}\) is True, so the next digit in $b$ is 1 and update $n$ to be \(\textcolor{blue}{157} - \textcolor{red}{128} = \textcolor{blue}{29}\).

\(2^6 = \textcolor{red}{64}\). \(64 <= \textcolor{blue}{29}\) is False, so the next digit in \(b\) is 0.

\(2^5 = \textcolor{red}{32}\). \(32 <= \textcolor{blue}{29}\) is False, so the next digit in \(b\) is 0.

\(2^4 = \textcolor{red}{16}\). \(16 <= \textcolor{blue}{29}\) is True, so the next digit in \(b\) is 1 and update \(n\) to be \(\textcolor{blue}{29} - \textcolor{red}{16} = \textcolor{blue}{13}\).

\(2^3 = \textcolor{red}{8}\). \(8 <= \textcolor{blue}{13}\) is True, so the next digit in \(b\) is 1 and update $n$ to be \(\textcolor{blue}{13} - \textcolor{red}{8} = \textcolor{blue}{5}\).

\(2^2 = \textcolor{red}{4}\). \(4 <= \textcolor{blue}{5}\) is True, so the next digit in \(b\) is 1 and update $n$ to be \(\textcolor{blue}{5} - \textcolor{red}{4} = \textcolor{blue}{1}\).

\(2^1 = \textcolor{red}{2}\). \(2 <= \textcolor{blue}{1}\) is False, so the next digit in \(b\) is 0.

\(2^0 = \textcolor{red}{1}\). \(1 <= \textcolor{blue}{1}\) is True, so the next digit in \(b\) is 1 and update \(n\) to be \(\textcolor{blue}{1} - \textcolor{red}{1} = \textcolor{blue}{0}\).

Hence the binary representation of 157 is 100110101.

\(2^7\)
\(128\)
\(2^6\)
\(64\)
\(2^5\)
\(32\)
\(2^4\)
\(16\)
\(2^3\)
\(8\)
\(2^2\)
\(4\)
\(2^1\)
\(2\)
\(2^0\)
\(1\)

1

0

0

1

1

1

0

1

Note

There are only 10 types of people in this world. Those who understand binary and those who don’t!

Question 1

Suppose you wanted to convert the binary number 110001101 to decimal. Which fills out the following tables correctly?

\(2^8\)
\(256\)
\(2^7\)
\(128\)
\(2^6\)
\(64\)
\(2^5\)
\(32\)
\(2^4\)
\(16\)
\(2^3\)
\(8\)
\(2^2\)
\(4\)
\(2^1\)
\(2\)
\(2^0\)
\(1\)

  1. \(2^8\)
    \(256\)
    \(2^7\)
    \(128\)
    \(2^6\)
    \(64\)
    \(2^5\)
    \(32\)
    \(2^4\)
    \(16\)
    \(2^3\)
    \(8\)
    \(2^2\)
    \(4\)
    \(2^1\)
    \(2\)
    \(2^0\)
    \(1\)

    1

    0

    1

    1

    0

    0

    0

    1

    1
  2. \(2^8\)
    \(256\)
    \(2^7\)
    \(128\)
    \(2^6\)
    \(64\)
    \(2^5\)
    \(32\)
    \(2^4\)
    \(16\)
    \(2^3\)
    \(8\)
    \(2^2\)
    \(4\)
    \(2^1\)
    \(2\)
    \(2^0\)
    \(1\)

    1

    0

    0

    1

    1

    1

    1

    0

    1
  3. \(2^8\)
    \(256\)
    \(2^7\)
    \(128\)
    \(2^6\)
    \(64\)
    \(2^5\)
    \(32\)
    \(2^4\)
    \(16\)
    \(2^3\)
    \(8\)
    \(2^2\)
    \(4\)
    \(2^1\)
    \(2\)
    \(2^0\)
    \(1\)

    0

    1

    0

    1

    0

    0

    1

    1

    1
  4. \(2^8\)
    \(256\)
    \(2^7\)
    \(128\)
    \(2^6\)
    \(64\)
    \(2^5\)
    \(32\)
    \(2^4\)
    \(16\)
    \(2^3\)
    \(8\)
    \(2^2\)
    \(4\)
    \(2^1\)
    \(2\)
    \(2^0\)
    \(1\)

    1

    1

    0

    0

    0

    1

    1

    0

    1
Solution

D.

To correctly fill out the table, we just want to write our binary number 110001101 along the bottom row with one digit in each box.

Question 2

What is the binary number 110001101 as a decimal number?

Solution

Solution is locked

Question 3

Consider the decimal number \(38\). What is the highest value of \(x\) for which \(2^x <= 38>\)?

Solution

Solution is locked

Question 4

What is the binary representation of the decimal number 38?

\(2^8\)

\(2^7\)

\(2^6\)

\(2^5\)

\(2^4\)

\(2^3\)

\(2^2\)

\(2^1\)

\(2^0\)

\(256\)

\(128\)

\(64\)

\(32\)

\(16\)

\(8\)

\(4\)

\(2\)

\(1\)
Solution

Solution is locked

Code Challenge (Extension): Converting Between Binary and Decimal

Write a module called conversions that can be used to convert from binary to decimal and vice versa. You should be able to import functions from your module into your main script main.py. Your module should contain the following 2 functions.

Binary to decimal specification (written in conversions.py)

  • name: bin_to_dec

  • parameters: n (int)

  • return: n as a decimal number (int)

Decimal to binary specification (written in conversions.py)

  • name: dec_to_bin

  • parameters: n (int)

  • return: n as a binary number (int)

Example 1 (running from main.py)

import conversions

print(conversions.bin_to_dec(10101))
print(conversions.bin_to_dec(10011101))

21
157

Example 2 (running from main.py)

import conversions

print(conversions.dec_to_bin(21))
print(conversions.dec_to_bin(157))

10101
10011101

Example 3 (running from main.py)

import conversions

for i in range(10):
    print(conversions.dec_to_bin(i))

0
1
10
11
100
101
110
111
1000
1001
Solution

Solution is locked