PGSS Computer Science Core

In lecture and in the course notes, the wrong assumption was made that students would have seen binary numbers before. Here we explain how binary numbers work much more thoroughly.

## Representation

As beings that normally have 10 fingers, humans work with base-10 numbers. It's no coincidence that we call both our fingers and the characters '0' through '9' digits. We write our numbers using these digits, but the choice of 10 is basically arbitrary. We call this base-10 numbering system the decimal number system.

When we write the number 4096, this actually represents 4 thousands, 0 hundreds, 9 tens, and 6 ones. (Maybe you remember going over this in painfully great detail in grade school.) Another way to write the same thing is

4 * 10^3 + 0 * 10^2 + 9 * 10^1 + 6 * 10^0
(I'm using '^' to represent exponentiation, normally done as superscripts. (HTML doesn't do superscripts.))

Computers use bits, not digits, however. Bits can only be '0' or '1'. For this reason computers use base 2, also called the binary number system.

In the binary number system, when we write a number 11010, each place represents a power of 2, just as each place represents a power of 10 in the decimal number system. The right-most bit is the 1's place; the bit to its left is the 2's place, the bit to its left is the 4's place, then the 8's place, the 16's place, the 32's place, the 64's place, the 128's place, and so on. So we translate 11010 to mean 1 sixteen, 1 eight, 0 fours, 1 two, and 0 ones, or, again,

1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0
To see what 11010 is in the decimal numbers we know and love, we can reeevaluate this in base 10: 16 + 8 + 0 + 2 + 0 = 26.

(Notice that there's nothing sacred about 10 and 2; in fact, we can write numbers in any base we want.)

We add binary numbers just like we add decimal numbers, using the technique you learned in grade school. But now we add bits in binary, so 1 + 1 = 10 (the binary representation of 2), and 1 + 1 + 1 = 11 (the binary representation of 3).

Let's look at an example. We want to add 1011 and 111. (Verify that these are decimal 11 and 7.) We begin at the 1's place, and note that 1 + 1 = 10. We place the last bit of 10 in the 1's place of the solution and carry the rest (a 1) to the 2's place.

```        1
1011
+  111
------
0
```
Now we look at the 2's place. We see 1 + 1 + 1 = 11. So we write a 1 in the 2's place of the answer and carry the 1.
```       1
1011
+  111
------
10
```
We examine the 4's place. 1 + 0 + 1 = 10. Write 0 in the 4's place and carry the 1.
```      1
1011
+  111
------
010
```
The 8's place is next. 1 + 1 = 10. 0 goes in the 8's place, and we carry the 1.
```     1
1011
+  111
------
0010
```
Finally, in the 16's place we have only a 1 to put into the answer.
```      1011
+  111
------
10010
```
You can see that this is the binary representation of 18, the sum of 11 and 7.

## Multiplying binary numbers

Again, we can multiply binary numbers just as we learned to multiply decimal numbers in grade school. Indeed, the multiplication table for just zeroes and ones is much easier!

Say we want to multiply decimal 11 and 5 in binary. Their binary representation is 1011 and 101. We write them both, and begin with the 1's bit of the multiplier (5). Since this is a 1, we write 1 times 1011 below the line.

```        1011
*    101
--------
1011
```
Now the 2's bit of the multiplier is 0. So we write 0 times 1011 below that, shifted left one place.
```        1011
*    101
--------
1011
0000
```
Finally, the 4's bit is a 1. We write 1 times 1011 below that, shifted left one place.
```        1011
*    101
--------
1011
0000
1011
```
```        1011