2023-09-03 - DataTypes: Binary Arithmetic

DataTypes

• Part 1 - Introduction
• Part 2 - Bits
• Part 3 - Logical Values
• Part 4 - Numbers
• Part 5 - Binary Arithmetic
• Part 6 - Negative Numbers

Last time I said we would talk about negative numbers next but I realized I should probably explain binary arithmetic first. It's easier to show negative numbers working if you understand how binary math with positive numbers works. So that's what we are going to do today.

Binary arithmetic is actually easy. It mostly works the same as decimal arithmetic except we only have two digits instead of ten.

Lets start with a simple addition example, 8 + 3. In binary that's 1000 + 11. We setup the equation as we would normally and just go through the steps of adding each digit together in turn.

We start on the right hand side and get 0 + 1 = 1. Fairly basic math. This is the same for the second digit as well. Then we have a 0 which just drops down and the 1 does the same. This gives us 1011 which is 11 in decimal. 8 + 3 = 11 and 1000 + 11 = 1011.

Now let's look at something a bit more complicated, 15 + 25. In binary that would be 1111 + 11001.

Again we start on the right hand side. 1 + 1 = 10 (2) which means the result is 0 and we have a carry of 1. Carries work the same as they do in decimal math, they simply get added to the next digit. The next two digits are the same due to the carry being included in the addition. The fourth digit is 1 + 1 + 1 with the third 1 being the carry. 1 + 1 + 1 = 11 (3) so the result is 1 with a carry of 1. We then again have 1 + 1 = 10 and that gets added to the result which is 101000 or 40 in decimal.

As you can see the combination of digits is very limited. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10. The most complicated calculation to do is 1 + 1 + 1 = 11 if both digits are 1 and we have a carry.

Now let's look at subtraction with 19 – 3.

We start with 1 – 1 = 0. This is the same for the second digit as well. Then we have 0 – 0 = 0, 0 – 0 = 0 and 1 – 0 = 1. This gives us 10000 or 16.

Now let's look at 20 – 3. That would be 10100 - 11

We again start with the right and do 0 – 1 which can't be done so we borrow from the next digit but the next digit is also 0 so it also needs to do a borrow. The third digit in the top number is a 1 so it can be used for borrow and becomes 0. Then working back the second digit becomes a 10 because of the borrow but we need to borrow from it so it becomes a 1 because 10 – 1 = 1. Now we have a 10 for the first digit and we can finally subtract the 1 so we do 10 – 1 = 1 again. For the next digit we have  1 – 1 = 0 and the rest of the digits just drop down to give us 10001 or 17.

Multiplication works like you would expect. Let's look at 26 x 3 which would be 11010 x 11.

With decimal multiplication you multiply the top number by each digit in the bottom number and then sum the results. Each intermediate result has one more 0 than the previous one. This is because each digit is 10 (or 2 for binary numbers) times bigger than the last. Binary multiplication works the same way. You start with the right most digit and multiply the top number by that. In this case the digit is a 1 so we just write down the top number as our first intermediate result. The second digit is also a 1 but we're in the 2's position now so we write down the top number with an extra 0 as our second intermediate result. This is effectively 26 + 26 x 2. Adding the two numbers we get 1001110 which is 78 or 26 x 3. Because binary only has two digits it's easy to come up with the intermediate values. They are either 0 because the digit is a 0 or the number shifted over a number of times because the digit is a 1. You can end up with a lot of additions to do if you have large numbers but the process is simple.

Division is similar. The number either fits and you put a 1 in the result or it doesn't and you put a 0. For example let's look at 30 (11110) divided by 8 (1000).

Like with decimal long division we consider more and more digits of the dividend until the divisor fits into it. Unlike decimal division we don't have to worry about knowing the multiples of the divisor. It either fits and the result gets a 1 or it doesn't and it gets a 0. After moving over three times we get 1111 which is bigger than 1000. So we subtract 1000 from 1111 to get 111 and then pull down the 0 from the dividend to get 1110. We then use this value and repeat the process. 1110 is greater than 1000 so we put another 1 in the result and take the difference. Pulling down another 0 we get 1100. Do it again and we get 1000. Once more and we get 0. Just as with decimal division the decimal point in the dividend and the quotient is the same. This gives us a result of 11.11. We'll look at fractional numbers later but for now just believe me when I tell you this is 3.75, the result of dividing 30 by 8.

Notice that we basically just shifted 11110 over 3 digits to get 11.11. This is because we divided by 8 which is a power of 2. This is the same as dividing a decimal number by powers of 10.

Note that computers don't actually do math step-by-step like this. They either use algorithms to speed up the process or have logic implemented in circuits which can determine the result electronically. For example the result of adding two digits (A and B) and a carry (C) is (A XOR B) XOR C. The result is 1 if either of the inputs are 1 unless the carry is also 1. The carry out logic is a bit more complicated but can still be implemented with simple logic gates.

It's also important to remember that computers mainly work on numbers with a fixed number of digits. This means that if a numbers get to big it ends up wrapping around because there's no more digits for it to grow into. Earlier we looked at 1111 + 11001 and got 101000 but if the this was a 5-bit computer the result would actually be 01000. That's because the largest value that can be stored in 5 bits is 31. The math is the same but the carry out from the final 1 + 1 is lost.

Computers actually use this as a trick to implement negative numbers as we will see next time when we look at how computers implement negative numbers. I promise will will actually do it this time.