Binary Math
Binary Math¶
We can do math using any base. All the same basic ideas you learned in grade school can be applied. When we add two digits together, we can get a two digit answer. One digit is the carry digit. It propagates to the next column. The other digit is the result digit.
For example, if you added \(7_{10} + 5_{10}=12_{10}\) we would say the result digit for this column is 2 and the carry digit is 1.
When adding multiple digits together, each column is handled starting from the rightmost. The carry digits propagate to the left. Before diving into binary addition, let us do a classical addition first.
We want to add 17 + 25.
\( \begin{align} & 10 & \text{(Carry)} \\ & 17 & \text{(Value 1)} \\ +& 25 & \text{(Value 2)} \\ & = \\ & 42 & \text{(Result)}\\ \end{align} \)
We start with a carry of 0. The least significant digits are 7 and 5. The rightmost column shows that 0+7+5=12. The result digit 2 is the answer for this column. The carry digit 1 is propagated to the second column. The second column is 1+1+2=04. The result digit is 4. The carry digit is 0. Since the carry digit is 0 and there are no additional value digits we are done the addition.
This same pattern will be used with binary addition. Each column of addition will still be the addition of 3 digits (two values and a carry). Since there are only two possible digits, we can easily write out all possible options.
Addition |
Carry |
Result |
|---|---|---|
0 + 0 + 0 |
0 |
0 |
0 + 0 + 1 |
0 |
1 |
0 + 1 + 0 |
0 |
1 |
1 + 0 + 0 |
0 |
1 |
1 + 1 + 0 |
1 |
0 |
1 + 0 + 1 |
1 |
0 |
0 + 1 + 1 |
1 |
0 |
1 + 1 + 1 |
1 |
1 |
Combining this with what we already know about addition, we can add binary numbers. The below example shows a classical addition and a binary addition. Notice that the pattern is the same in both cases.
\( \begin{align} & 10 & & 0011 1000 & \text{(Carry)} \\ & 28 & & 0001 1100 & \text{(Value 1)} \\ +& 7& +& 0000 0111 & \text{(Value 2)} \\ & = & & = & \\ & 35 & & 0010 0011 & \text{(Result)}\\ \end{align} \)
We can look at a smaller addition in more detail. We will just add \(01_{2}+11_{2}\). The values have be padded with leading zeros.
\( \begin{align} & 110 & \text{(Carry)} \\ & 001 & \text{(Value 1)} \\ +&011 & \text{(Value 2)} \\ & = & \\ & 100 & \text{(Result)} \\ \end{align} \)
We computed \(1_{10}+3_{10}=4_{10}\) in binary.
Note
Computer hardware can only add with certain numbers of bits. It depends on the number of wires in the circuit. Zeros can always be added to the front of a number to pad it out.
We can analyze exactly what happened with our addition.
The first carry is always 0. 0+1+1=10. In binary, \(2_{10}=10_{2}\).
The second column is 1+0+1=10. The carry propagated from the rightmost column.
The leftmost column is 1+0+0=01. It only has the carry from the previous column.
An interesting thing happens in this example. The result has more digits then the inputs! The input numbers had two digits, the result was three digits. In classical paper addition, this would be fine. On physical computer hardware it might be a problem.
As we saw earlier, a computer needs a physical wire for each bit (digit) it stores. If the computer only had two wires, there would be nowhere to put the third column. The physical limitation of the computer would make this addition impossible. A carry that cannot be handled by the computer is called overflow. When we run out of bits, the carry overflows the processor’s wires.
If we only had a 2 bit computer, the previous addition would look a little different.
\( \begin{align} 1& 10 & \text{(Carry)}\\ & 01 & \text{(Value 1)} \\ +&11 & \text{(Value 2)} \\ & = & \\ & 00 & \text{(Result)} \\ \end{align} \)
We would compute \(1_{10} + 3_{10} = 0_{10}\). We just don’t have space to store the last carry.
On an 8-bit computer, it is impossible to add two numbers and get a 9-bit answer. The computer is limited to 8-bits. If the answer is to big, the computer overflows and we get an incorrect answer.
All modern processors have a way for the programmer to determine when an overflow has taken place. A modern 64-bit computer could work with positive integers from 0 to 18,446,744,073,709,551,615. We need to be aware of overflow, but it is not as immediate an issue as it was with 8-bit computers.
We can also multiply numbers in any base. In binary, multiplication is very straightforward. We only multiply by either 0 or 1. We will multiply \(9_{10}*5_{10}=45_{10}\) in binary. The computation will be completed in 8-bits.
\( \begin{align} & 0000 1001 & \text{(9 in Binary)} \\ *& 0000 0101 & \text{(5 in Binary)} \\ & = & \\ & 0000 1001 & \text{(1 * 9 shifted zero times)} \\ +& 0000 0000 & \text{(0 * 9 shifted left once)} \\ +& 0010 0100 & \text{(1 * 9 shifted left twice)} \\ +& 0000 0000 & \text{(0 * 9 shifted left three times)} \\ +& \cdots & \text{(all addition values are 0s)} \\ & = & \\ & 0010 1101 & \text{(sum of binary values)} \\ \end{align} \)
The result of this multiplication is 0010 1101. Converting back to base-10, we get
\( \begin{align} 32+8+4+1=45 \end{align} \)
The rules we learned in grade school multiplication also apply to binary multiplication. More generally, we can abstract the rules to any base system.