Binary numbers

We use a List[Int] to represent binary numbers, a list of 0's and 1's. If you pass in a list that has any other numbers except 0 or 1, the algorithms will throw an exception.

Before we look at the summation and multiplication operations, let's look at how to handle the carry operation. For example, when you add 1 to 1011 (decimal 11), you get 1100 (decimal 12). Here is how a carry is propagated:

Before we try modeling the binary numbers as a list, there is a caveat we need to be aware of!

We write a binary number from left to right. In other words, the most significant bit is at the leftmost and the least significant bit of a binary number is at the rightmost.

To add a carry, we typically start from the right; however, as we have already seen, for a list, that would be the tail. Working on a list tail is expensive. Instead, we want to work at the head of the list and express operations using list prepend. This means we need to reverse the list so we can both...