Prelude to part 2 – Binary Arithmetic
There are two primary functions that a CPU must have in order to be useful, those being arithmetic and logic. Both arithmetic and logic are performed in a CPU through the use of logic gates, which we discussed in the previous part. Logic gates, as we’ve seen already, operate on one’s and zero’s, binary.
If we’re going to implement our own virtual CPU then, we’ll need an understanding of how to perform arithmetic and logic operations using binary. We’ve already touched on binary logic in the previous section on logic gates, so in this part then, we’ll take a look at how to perform arithmetic using binary.
Now, if you’re a regular follower of my blog or YouTube channel, you’re likely already a software developer or engineer, and likely already have some understanding of how binary works. If this is you, then please feel free to skip ahead. For everyone sticking around however, I’d like to explain the premise for the way that I plan to teach you about binary.
Coco the computer.
Binary is a numbering system just as decimal is. I expect that just about everyone reading this has an understanding of the decimal numbering system, after-all, it’s the numbering system that most of us count in. The easiest way to teach any subject is by relating the new subject to a common frame of reference, building on existing knowledge. The easiest way to teach binary then, is to relate it back to decimal. As I began to do this for the video, I came across a problem – No matter how hard I tried, I couldn’t find a way to teach binary that didn’t feel somewhat patronizing. I essentially had to review our knowledge of decimal, which the majority of you will have attained as a young child. As I didn’t want to come across as patronizing, I decided instead to have my own childhood mentor do the teaching!
When I was a young child, around five years old, my parents bought for me an 8-bit programmable computer. It was a Tandy TRS-80 Color Computer 2, which fans of the computer later nick-named ‘Coco’ as an abbreviation of ‘Color Computer’. This machine came with a programming manual named “Getting Started in Color Basic” which featured a little computer/robot character as it’s illustration. I decided to name this little guy “Coco” after the computer he was based on, and for my video, I animated Coco teaching binary.
What follows then, for the remainder of this part, is a transcript of Coco teaching binary arithmetic!
Coco teaching binary arithmetic, transcript…
Hi, My name is CoCo.
Today, I’m going to teach you all about binary.
You’ll learn how to convert numbers from decimal to binary, and back again.
And you’ll learn how to do addition in binary.
In fact, by the time we’re done, you won’t need cumbersome decimal anymore!
You humans count in decimal.
Decimal has ten symbols, called numerals, to represent any number from zero through to nine.
Lets count together.
One, Two, skip a few, eight, nine…
Oh! We’ve run out of numerals!
To keep on counting, we start back at zero and place a one to it’s left.
Ten, Eleven, and so on…
When we have more than one numeral in a number like this, we call each position a digit.
Each digits position indicates it’s significance.
For example, in the number 23, the first digit represents two tens, and the second digit represents three ones.
The number of numerals in a numbering system is called it’s “base.”
Because decimal has ten numerals in it’s base, and the position of a digit changes it’s significance, we call decimal a
“base-ten positional numbering system.”
The last digit position in a positional numbering system is called the unitary digit.
The unitary digit always has a significance of one, because it represents the number of ones.
The significance of each digit to the left, is a power of the base.
So for decimal, if we start at the unitary digit, and move one digit to the left, we multiply one, by the base, ten, giving the next digit to the left, a significance of ten.
Lets do it one more time.
Starting in the ten’s digit position, we multiply by the base, ten, and we get one hundred, making the next digit to the left, the hundreds digit.
See!
Okay, you’re doing great.
Now lets talk about Binary!
Binary is a base-two positional numbering system.
That means, that there are only two numerals, and their position changes their significance.
It’s just like decimal, but with only the numerals zero, and one.
Just so you know, in binary we don’t use the word “Digit.”
This is because the word “digit” is derived from the latin word “digitus” meaning “finger” or “toe”.
The decimal numbering system was designed to allow you to count using your fingers or toes!
Heh! you humans do amuse me!
Most computers don’t have fingers, so in binary, we use the word “Bit” instead.
The position of each bit has significance, just as in decimal, but because binary is base-two, the significance of each bit is calculated in multiples of two, instead of ten.
Take a look. From right to left we have one, two, four, eight, sixteen, and so on…
If we have the number one, zero, one, the left most bit means that there is one four, the middle bit that there are no twos, and the third bit that there is one one.
Also note that we read the number as three bits, “one-zero-one.” This is to avoid confusing the number with the decimal number one-hundred and one. In decimal, this is actually the number five.
I’ll bet you’ve realized this already, but binary numbers are a lot longer than decimal. “one-zero-one” is a three bit number in binary, but only a single digit, “5” in decimal.
Lets convert a number from decimal, into binary together. We’ll convert the number one-hundred and seventy three. In decimal, the number one-hundred and seventy three is a three digit number, but in binary, it will be eight bits wide. So we’ll start with our eight positional bit columns, like this…
The first bit, counts the number of one-hundred and twenty eights.
Well, one-hundred and twenty eight fits just one time into one-hundred and seventy three. So, we put a one in that bit position, and we subtract one-hundred and twenty eight, from our one-hundred and seventy three, leaving a remainder of forty five.
The next bit position is the number of sixty fours that will fit into your remaining forty five. Well, sixty four doesn’t fit into forty five, so this bit is a zero.
On-to the next bit.
How many thirty-twos fit into forty five? Just one, so we write a one and subtract thirty two from forty five, leaving a remainder of thirteen.
Our next bit position is the number of sixteens that fit into our remainder of thirteen. So again, we have a zero and we move on.
Our next bit position is the number of eights. Well, there’s one eight in thirteen, so we write a one and we have a remainder of five.
The next bit position is the number of times four fits into our remainder of five, so that’s a one, and we have a remainder of one.
The next bit position is the number of times two fits into our remainder of one. So, that’s another zero,
And our final bit position is the number of ones remaining, so we write a one and subtract it to leave us with zero.
And that’s it!
We just converted the number one-hundred and seventy three into binary!
I did cheat a little for you though, you see, I already know that one-hundred and seventy three takes eight bits, so I made sure we had enough to work with.
When you’re converting decimal numbers into binary, for use in computer programming, you can follow this simple rule.
“You can’t put a numeral other than zero or one into any bit position. So, if the first bit positions significance, in our example, one-hundred and twenty eight, fits into your decimal number more than once, you’ll need more bits.”
Generally, computers use arrangements of eight, sixteen or thirty-two bits to store numbers of different sizes. For the mathematicians among you, you can calculate the precise number of bits required to store any number. The formula goes like this. “Number of bits equals, the ceiling of, the log base-2 of, the decimal to be converted…”
Now lets prove that we got our conversion to binary right, by converting it back to decimal.
Converting from binary to decimal is even easier. To convert from binary to decimal, we simply add together the bit significance of each bit position that has a one in it. In our case, we add one-hundred and twenty eight, thirty two, eight, four and one…
One hundred and twenty eight, plus thirty two, is one hundred and sixty.
Plus eight, is one hundred and sixty eight.
Plus four, is one hundred and seventy two.
And plus one is one hundred and seventy three.
See how easy that was?!
Now that you’re an expert at converting numbers from decimal to binary, lets look at how we do addition in binary.
We’ll add the numbers two and nine, to get eleven.
Two in binary is zero, zero, one, zero.
Nine in binary is one, zero, zero, one.
We do addition in binary in much the same way as we’d do it in decimal.
Starting on the right, and working back to the left. We add each pair of bits.
Zero plus one is one…
One plus zero, is one.
Zero plus zero, is zero.
And, zero plus one, is one.
So our result is, one, zero, one, one.
Go ahead and convert that back to decimal, do you get eleven like I did?
Great!
Lets try another example. This one is just a little bit tricky, but I’m sure you’ll get the hang of it.
This time, we’re going to add three to nine, sounds simple enough right?
Well, three in binary is zero, zero, one, one.
And we’ve already seen nine in binary, is one, zero, zero, one.
So lets start with the right-most bits, and work backwards again.
One and one is… I’ll bet you’re tempted to say two right?
Well, remember that this is binary. We don’t have a numeral for two.
In binary, two is represented as one, zero.
So we have a two bit result for the addition of our right most bit.
What should we do?
Well, we do the same as we’d do in decimal.
If we add two single digits, say five and six, to get a two digit result of eleven,
we use a carry to move the most significant digit back to the left.
Lets add a carry bit to our diagram…
Okay, lets start over in the right-most bit.
One plus one is, carry-one, and zero.
Great!
Now we just add up the next bit to the left, remembering to include the carry.
One plus one plus zero, is again, a carry and a zero.
The third bit is one, plus zero, plus zero, so that’s a one.
The final bit is zero plus one, that’s also a one.
So our result is one, one, zero, zero.
Sure enough, that’s twelve in decimal.
Good Job!
Wow, we’re almost done learning to convert to and from binary, and to do some simple arithmetic, but there’s one more thing we should look at. Subtraction.
If you think about it, when you know how to do addition and subtraction, you can also do multiplication and division.
In order to multiply, you just keep adding…
and to do division, you keep subtracting until you reach zero.
So if we just learn to do subtraction in binary, you’ll be able to perform all four arithmetic operations.
The good news is, that you already know how to do subtraction, you just may not have realized it yet.
Consider subtracting six from nine in decimal.
Normally, you’d write it like this; “nine minus six”
Okay, but there’s another way to write it, like this; “nine plus negative six.”
Whenever you add a negative number, you get the same result as if you’d subtracted the positive of the same number.
This remains true in binary, so you can already do subtraction by performing the addition of a negative number.
All that you need to understand then, is how to represent a negative number in binary.
There are several schemes for representing negative numbers in binary, but they don’t all work for our addition and subtraction operations. We’re going to walk through three different schemes for representing negative numbers, until we get to the one that works for addition.
The first scheme appears fairly obvious, and it’s called “Signed Magnitude.”
Consider the number six in binary; one one zero.
Signed Magnitude says that in order to specify if this number is positive or negative, we simply add a bit to the left.
This new “left bit” is not a part of the number, it’s simply a flag to indicate the sign of the number.
When it is set to zero, the number is positive…
and when it is set to one the number is negative.
So positive six becomes zero, one, one, zero, and negative six becomes one, one, one, zero.
This scheme is very simple, and it has the advantage that it does not actually change the representation of positive numbers. Because positive numbers are written without any trailing zeros, the positive sign bit is simply omitted, leaving the original binary number.
The problem with this scheme of signed magnitude is that it doesn’t work correctly for the arithmetic. Lets add the positive and negative representations of six, using the addition technique we learned earlier, to see the problem.
Zero plus zero is zero.
One plus one is carry one and zero.
The carried one, plus one, plus one, is carry one and one.
The carried one, plus zero, plus one is carry one and zero.
So we get a result of one, zero, one, zero, zero.
Taking the first bit as the sign, we have the curious result of negative zero, one, zero, zero, or in decimal, negative four.
Clearly, this as not worked, but we can do better.
The second scheme we’re going to look at is called “One’s Compliment.”
It works in a similar way to signed magnitude, but gets us closer, though not entirely, to the desired result.
To create the negative of a number in one’s compliment, we still add a sign bit, just as we did for signed magnitude, but then we flip all of the bits after the sign bit. That-is, the zeros become ones, and the ones become zeros.
So the number six in one’s compliment is still zero, one, one, zero and negative six becomes one, zero, zero, one.
Again, we’ll perform the addition of negative six to positive six.
Zero plus one is one.
One plus zero is one.
One plus zero again, is one.
And Zero plus one is one.
So we end up with, four ones.
The first one is the sign bit, and it’s negative, which means we need to flip all of the bits after the sign bit.
This gets us back to one, zero, zero, zero.
If we ignore the sign bit, we can see that we got the correct result of zero, but we still have a problem.
The sign bit is still one. According to one’s compliment rules, the answer is negative zero.
The number zero sits between the positive and negative numbers of any numbering system, it has no sign.
Using one’s compliment however, there are two possible combinations of bits which represent zero.
What’s the solution?
Two’s Compliment!
To get the two’s compliment of a number, we take the one’s compliment and add one.
It’s that simple!
So lets subtract six from six again, by adding the two’s compliment of negative six to positive six.
Six is represented as zero, one, one, zero.
We get the one’s compliment negative by setting the first bit to one; and flipping the remaining bits.
One, zero, zero, one.
To get the two’s compliment, we add one.
One plus one is carry one and zero.
So we get one, zero, one, zero.
Now let’s add the two values…
Zero plus zero is zero.
One plus one is carry one and zero.
The carried one, plus one plus zero, is carry one and zero.
The carried one, plus zero, plus one is carry one and zero.
In this case we carried one into the sign bit, and also got a carry out, but because the sign bit is not a part of the number, we can simply drop the carry out. This leaves us with a result of zero, zero, zero, zero.
We now have our correct answer.
We are now able to perform subtraction in binary numbers by simply flipping the sign of the term on the right, and performing addition instead.
You now have the knowledge to convert numbers from binary to decimal and back.
You can perform addition and subtraction, and with a little repetition, you can perform multiplication and division too.
There’s just one thing left. We’ve only looked at how whole numbers work, what about fractional numbers?!
Well that’s a whole other discussion, and now that I’ve got you started in binary, I think I’ll let Craig have that discussion with you, when you’re ready.
As for me, well, another of my students is struggling with sorting algorithms. I’m going to hop on over there and help her out.
Goodbye Craig!
Good luck with your Virtual Machine project.
