12-31-2013, 02:20 AM
So recently for the line algorithms in my upcoming GPU, I found myself requiring a two's complement adder. I sort of skated around building it because it seemed foreign and strange to me, and many of the tutorials I found gave me only a piece of the puzzle. Today I'd like to give you the whole picture all at once, in understandable terms for redstone. I'm still learning more advanced signed operations such as optimized comparison, subtraction, and mult/div, so this thread will be updated with tutorials as I myself learn the concepts.
What is two's complement?
You've heard the term time and time again, you know it makes a number negative, but what really is two's complement? Two's complement is essentially an intuitive representation of a negative binary number with altered bits and a sign. Many devices, such as subtractors, natively return outputs in two's complement, which is why it is so widely used.
Conversions
Note: Numbers' sign bits will be shown on every binary number I represent, as the first bit. It will be in italics. It's good to know that 0=positive and 1=negative.
Let's say we have the positive binary number 01010, and we want to negate it using the simple system of two's complement. This is a two-step process that you've probably heard all the time when making binary subtractors, which are actually just adding the two's complement negative. (Fun fact!
)
Well first let's figure out what 01010 is in binary, 8+2=10 decimal, if you don't know binary then that's a definite prerequisite to two's complement. We've got a bunch of tutorials laying around the forums.
Okay, so now we have our 01010. Time for the process! It's the two-step subtractor process:
1. Invert all the bits.
2. Add 1.
3. Profit!
So let's do this with our 10 decimal. We start with 01010, inverting all bits gives us 10101. (Yes, we also invert the sign bit! Which makes sense, since we're just making the number negative.) Now, we can add 1:
10101
+0001
-------------
10110
And this answer is indeed 01010 in two's complement! You can use this process to convert negative to positive as well.
Addition
HEY! LISTEN! HEY!: You must must must know binary addition for this. I'm not going to explain the binary addition process for this, only how it applies to two's complement.
Alright, so at first the concept of two's complement addition is a lot like regular binary addition that just includes the signs, with the COUT truncated. There's some extra crap that can happen, but if I could I would make all adders two's complement, because it completely eliminates the need to make seperate adders and subtractors... they're the same!
So let's start by saying we want to add 7+(-3). Obviously, this simplifies to 7-3, so in the addition section we're already subtracting! Well, 7 in binary is 0111 and 3 is 0011.
But we need to convert 3 to two's complement! Let's do that!
0011 --> 1100 --> 1101! That's just a simple conversion, obviously you should read conversions before this.
Okay, so now let's add!
0111
+1101
10100
Wait... what? We just got 20... what just happened? Well, when adding two's complement we get this extra carry on the end that nobody cares about. We can simply get rid of the COUT 1 and get 0100. And that's positive 4, which is indeed 7-3. You can do this with most numbers, and you can literally implement this in redstone with little more than a simple adder. Just remember to use the signs in the addition and to discard the final COUT!
But are we done? Well, sadly... no. ;-; We have a slight problem which I'll now show you. Let's do 0111+0101.
0111
+0101
01100
We take off the extra COUT and get 1100... and that's 12 in binary, right? But wait! Why is that one there in our sign spot! This is certainly not a negative number!
And welcome to a very annoying part of two's complement arithmetic: sign extension. Basically, the idea is that if we add another extra bit to our number before the sign, the sign will stay in the sign spot and other things will stay out of it. Sign extension in two's complement is actually really easy: just copy the sign bit for all your extras. For instance:
+9: 01001 = 001001
In this example, we add an extra 0 (which is our sign).
-9: 11001 = 111001
In this example, we add an extra 1 (which is our sign).
Alright, so let's do our sign extension and try our problem again.
00111
+00101
01100
And look at that, folks! Our extra 1 is now in a normal bit. Thus we have just created a perfect algorithm for redstone two's complement adders. To sum it up:
A. Have two extra bits to the left both connected to the sign
B. Ignore the final COUT
Easy as they come! Because this is so simple, once again I'd like to recommend two's complement adders to be used everywhere due to their versatility. But that's just my thought.
Sign Extension Intuition
Because I was having so much fun writing tutorial, I decided to do a quick intuition on why the whole sign extension idea works. To recap, sign extension in two's complement is just taking the sign and copying it over however many times. For instance:
0101 = 000...0101
1101 = 111...1101
Well the first example is obvious, you can stick as many 0s at the front of a regular binary number as you want and it won't change. That's the easy part. But what about the second example? Well, we know that two's complement is pretty much an inverted form of a regular binary number, so if we convert that negative back to a positive all those extra 1s will become 0s when we invert.
I don't know, just kinda felt like putting that in there.
Subtraction
Well, if we can already add signed numbers, then we can add positive to negative. This gives us subtraction, so there's no need for a seperate two's complement subtraction.
More to come in the near future!
What is two's complement?
You've heard the term time and time again, you know it makes a number negative, but what really is two's complement? Two's complement is essentially an intuitive representation of a negative binary number with altered bits and a sign. Many devices, such as subtractors, natively return outputs in two's complement, which is why it is so widely used.
Conversions
Note: Numbers' sign bits will be shown on every binary number I represent, as the first bit. It will be in italics. It's good to know that 0=positive and 1=negative.
Let's say we have the positive binary number 01010, and we want to negate it using the simple system of two's complement. This is a two-step process that you've probably heard all the time when making binary subtractors, which are actually just adding the two's complement negative. (Fun fact!
)Well first let's figure out what 01010 is in binary, 8+2=10 decimal, if you don't know binary then that's a definite prerequisite to two's complement. We've got a bunch of tutorials laying around the forums.
Okay, so now we have our 01010. Time for the process! It's the two-step subtractor process:
1. Invert all the bits.
2. Add 1.
3. Profit!
So let's do this with our 10 decimal. We start with 01010, inverting all bits gives us 10101. (Yes, we also invert the sign bit! Which makes sense, since we're just making the number negative.) Now, we can add 1:
10101
+0001
-------------
10110
And this answer is indeed 01010 in two's complement! You can use this process to convert negative to positive as well.
Addition
HEY! LISTEN! HEY!: You must must must know binary addition for this. I'm not going to explain the binary addition process for this, only how it applies to two's complement.
Alright, so at first the concept of two's complement addition is a lot like regular binary addition that just includes the signs, with the COUT truncated. There's some extra crap that can happen, but if I could I would make all adders two's complement, because it completely eliminates the need to make seperate adders and subtractors... they're the same!
So let's start by saying we want to add 7+(-3). Obviously, this simplifies to 7-3, so in the addition section we're already subtracting! Well, 7 in binary is 0111 and 3 is 0011.
But we need to convert 3 to two's complement! Let's do that!
0011 --> 1100 --> 1101! That's just a simple conversion, obviously you should read conversions before this.
Okay, so now let's add!
0111
+1101
10100
Wait... what? We just got 20... what just happened? Well, when adding two's complement we get this extra carry on the end that nobody cares about. We can simply get rid of the COUT 1 and get 0100. And that's positive 4, which is indeed 7-3. You can do this with most numbers, and you can literally implement this in redstone with little more than a simple adder. Just remember to use the signs in the addition and to discard the final COUT!
But are we done? Well, sadly... no. ;-; We have a slight problem which I'll now show you. Let's do 0111+0101.
0111
+0101
01100
We take off the extra COUT and get 1100... and that's 12 in binary, right? But wait! Why is that one there in our sign spot! This is certainly not a negative number!
And welcome to a very annoying part of two's complement arithmetic: sign extension. Basically, the idea is that if we add another extra bit to our number before the sign, the sign will stay in the sign spot and other things will stay out of it. Sign extension in two's complement is actually really easy: just copy the sign bit for all your extras. For instance:
+9: 01001 = 001001
In this example, we add an extra 0 (which is our sign).
-9: 11001 = 111001
In this example, we add an extra 1 (which is our sign).
Alright, so let's do our sign extension and try our problem again.
00111
+00101
01100
And look at that, folks! Our extra 1 is now in a normal bit. Thus we have just created a perfect algorithm for redstone two's complement adders. To sum it up:
A. Have two extra bits to the left both connected to the sign
B. Ignore the final COUT
Easy as they come! Because this is so simple, once again I'd like to recommend two's complement adders to be used everywhere due to their versatility. But that's just my thought.
Sign Extension Intuition
Because I was having so much fun writing tutorial, I decided to do a quick intuition on why the whole sign extension idea works. To recap, sign extension in two's complement is just taking the sign and copying it over however many times. For instance:
0101 = 000...0101
1101 = 111...1101
Well the first example is obvious, you can stick as many 0s at the front of a regular binary number as you want and it won't change. That's the easy part. But what about the second example? Well, we know that two's complement is pretty much an inverted form of a regular binary number, so if we convert that negative back to a positive all those extra 1s will become 0s when we invert.
I don't know, just kinda felt like putting that in there.
Subtraction
Well, if we can already add signed numbers, then we can add positive to negative. This gives us subtraction, so there's no need for a seperate two's complement subtraction.
More to come in the near future!
