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.

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

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^0To 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 ------ 0Now 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 ------ 10We examine the 4's place. 1 + 0 + 1 = 10. Write 0 in the 4's place and carry the 1.

1 1011 + 111 ------ 010The 8's place is next. 1 + 1 = 10. 0 goes in the 8's place, and we carry the 1.

1 1011 + 111 ------ 0010Finally, in the 16's place we have only a 1 to put into the answer.

1011 + 111 ------ 10010You can see that this is the binary representation of 18, the sum of 11 and 7.

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 -------- 1011Now the 2's bit of the multiplier is 0. So we write 0 times 1011 below that, shifted left one place.

1011 * 101 -------- 1011 0000Finally, the 4's bit is a 1. We write 1 times 1011 below that, shifted left one place.

1011 * 101 -------- 1011 0000 1011We add these three lines together to get the answer.

1011 * 101 -------- 1011 0000 + 1011 -------- 110111The answer, converted to decimal, is 55, indeed the product of 11 and 5.