Welcome to the Geek Author series on Computer Organization and Design Fundamentals. I’m David Tarnoff, and in this series we are working our way through the topics of Computer Organization, Computer Architecture, Digital Design, and Embedded System Design. If you’re interested in the inner workings of a computer, then you’re in the right place. The only background you’ll need for this series is an understanding of integer math, and if possible, a little experience with a programming language such as Java. And one more thing. We’re going to be doing a bit of figuring in this episode, so it might help to keep a pencil and paper handy.
In Episode 3.3, “An Introduction to Twos Complement,” we made the leap from unsigned binary to signed binary representation. Twos complement representation not only allows us to represent negative integers using patterns of ones and zeros, it also fully supports addition for any combination of positive and negative values. This also makes it possible to perform subtraction using circuitry designed only for addition by changing the sign of the subtrahend and adding it to the minuend.
When we began discussing the topic of complementary arithmetic, we showed how the responsibility of the left-most digit of an integer goes from representing magnitude to representing the sign of the integer. In tens complement representation, for example, if the most significant digit is a zero, we have a positive number. If the most significant digit is a nine, we have a negative number. If we perform an addition in tens complement representation, any result with a most significant digit other than nine or zero means that an overflow had occurred, in other words, the result could not fit in the given number of digits.
There’s a problem, however, when we move to base two. In twos complement representation, we only have two numerals: zero and one. When the most significant digit is zero, the result is positive. When the most significant digit is one, we have a negative number. So how can we tell if an overflow has occurred?
Since an overflow means that our result has gone outside the range of what a fixed number of bits can represent, let’s see what the maximum and minimum integers are for an n-bit number in twos complement representation. We know that the largest integer must be a positive number, which means that the most significant bit must be a zero. The remaining n-1 bits are then treated as an unsigned binary integer. Therefore, for an n-bit twos complement integer, the maximum value is the same as the maximum value of an integer in unsigned binary with only n-1 bits, in other words, 2(n-1) – 1.
It’s not as obvious when it comes to determining the minimum decimal value that can be represented with twos complement representation using n bits. Since twos complement uses the most significant bit as a sign bit, and since the lowest value will be negative, the sign bit should be set to one. But what is to be done with the remaining bits? A natural inclination is to set all the bits after the sign bit to one. That should offer the largest magnitude, right? Let’s see.
To determine what negative value a twos complement integer represents, we must first flip the sign to positive to determine the magnitude. There were a couple of ways we could do this. The first method described was to invert each bit, then add one. When we take the bitwise inverse of an n-bit binary pattern made entirely of ones, we get an n-bit pattern of all zeros. Adding one to this result gives us, well, 1. This means that the integer represented by the twos complement number of all ones, regardless of the number of bits, is always negative one.
This isn’t quite what we expected, was it? If you go through all the possible patterns of ones and zeros, you’ll discover that the lowest possible twos complement value has a sign bit of one followed by all zeros. In the case of eight bits, this would be 10000000. Taking the bitwise inverse of 10000000 gives us 01111111. Adding one to that gives us 10000000. It seems that when we compute the additive complement of a twos complement value consisting of a one followed by all zeros, we get the same pattern back. This means that the decimal equivalent of the n-bit twos complement value of one followed by all zeros is –2(n-1). A little experimentation will show that this works mathematically too.
So how does this help us determine when an overflow has occurred in twos complement addition? A couple of examples might help. First, remember that the largest possible value we can represent in twos complement representation is a zero followed by all ones. If we add one to this value, we get a one followed by all zeros. This is a problem. We’ve added two positive numbers together and received a negative result. In actuality, we’ve had an overflow.
In our second example, let’s add the two most positive integers together to see what the result is. For any number of bits, the most positive integer in twos complement representation is a zero followed by all ones. Adding this value to itself always results in a binary value of all ones except for the last bit, which is a zero. As a side note, adding a value to itself is the same as multiplying that value by two. Recall from earlier episodes that a multiplication by a power of two has the same effect as shifting the binary number left by the number of bits equivalent to that power. Therefore, multiplying by two has the same effect as shifting left by one bit position, hence, we get a zero shifted in from the right, and all of the remaining bits to the left are one. This takes the most significant bit representing magnitude and shifts it into the sign bit position. This means that like the first example, we’ve added two positive numbers together and gotten a negative result. So, if the result of adding two positive numbers is negative, then result that cannot be contained in the fixed number of bits and we’ve had an overflow.
What may not be as obvious is that adding two negative numbers has the potential for wrapping around into the range of positive numbers. For example, adding the eight-bit number 10000000 to itself gives us a result of zero after discarding the carry. Zero has a sign bit of zero identifying it as positive, and just like before, the sign of our result has flipped. This gives us our method to determine if an overflow has occurred. If two twos complement values with the same sign are added, and the result has a different sign, then an overflow has occurred.
By the way, the result of adding a negative number to a positive number will always be a value that is between the two numbers added. That means adding numbers with different signs will never result in an overflow.
Let’s see if we can get an overflow to occur in an example. Negative sixty-one plus negative seventy-six is -137. If we perform this addition in 8-bit twos complement notation, we should get an overflow since -137 is more negative than the lower limit for 8-bit twos complement representation, which is -128.
Positive 61 in 8-bit twos complement is the same as positive 61 in unsigned binary: 00111101. Using our shortcut to flip the sign of a twos complement value, we start on the right side of the binary number, and going right to left, copy all the consecutive zeros along with the first one we get to. Since in this case the least significant bit is a 1, we only copy that bit. We invert the remaining bits to get 11000011. Positive 76 in 8 bits is 01001100. Using the shortcut to change it from positive to negative, we copy the three least significant bits, 100, then invert the remaining bits to get the final pattern of 10110100. Adding these two numbers together in binary gives us 11000011 + 10110100 = 101110111. Throwing away the carry into the ninth bit gives us 01110111, which is a positive value. That means that an overflow has occurred since both of our addends were negative.
In Episode 2.2 – Unsigned Binary Conversion, we discussed how shifting the bits of a binary number right is equivalent to dividing by powers of two while shifting the bits of a binary number left is equivalent to multiplying by powers of two. For example, if we shift the 8-bit binary representation of 5, which is 00000101, left by three bit places, we get 00101000, which is a decimal 40. This is equivalent to multiplying five by 23 or eight.
Does this still work in twos complement representation? As a matter of fact, it does. For positive numbers, as long as the leftmost one of the binary pattern doesn’t get shifted into the most significant bit or sign bit, the result remains positive and the operation behaves just as it does with unsigned binary.
But does this work if the binary pattern represents a negative number? Let’s look at a couple of examples. Forty-four in binary is 00101100. Applying the shortcut, we start on the right-side and copy down all of the consecutive zeros and the first one we get to when going from right to left. This means that the three least significant bits of negative forty-four are 100. We invert the remaining bits to get the 8-bit twos complement representation of -44: 11010100.
Shifting this pattern of ones and zeros one bit position left while continuing to limit ourselves to eight bits gives us 10101000, where we fill in the right side with a single zero and the sign bit drops off the left side. Let’s convert this 8-bit twos complement pattern to decimal to see if it works. The pattern 10101000 is negative, so to compute its decimal equivalent, we need to flip its sign before computing the magnitude. Using the shortcut to determine the additive complement, we see that the four least significant bits of the additive complement are 1000 while the four most significant bits are the inverse of 1010. This gives us 01011000. Adding the three powers of two represented by this positive number gives us 64 + 16 + 8 = 88. Therefore, 10101000 represents -88, which is two times -44.
If we shifted the 8-bit twos complement representation of -44 by two bit positions, we would have gotten 01010000. Unfortunately, the sign changed from negative to positive, which means we had an overflow. In other words, -44 times 4 is -176, which is beyond -128, the most negative value that can be represented by 8-bit twos complement notation.
Let’s see if right shifts of negative integers behave like division by shifting 11010100 two bit positions to the right. Here we see a difference between signed and unsigned binary. When we shift right, the bit value that we pull in from the left side must match the sign bit in order to maintain the sign of the value. For example, when we attempt to divide 11010100 by four by shifting two bit positions right, we need to fill in with two ones on the left. This gives us 11110101.
This pattern is negative, so to compute its decimal equivalent, we need to flip its sign before adding the powers of two. Using the shortcut to determine the additive complement, we see that there are no consecutive least significant zeros, so we only copy the least significant bit of one to our complement. The remaining seven bits are inverted. This gives us 00001011. Converting this to decimal by adding its powers of two gives us 8 + 2 + 1 or 11. That means 11110101 equals -11, which is -44 divided by four.
By the way, if you don’t believe that your computer treats signed binary integers the same way, play around with any calculator application capable of displaying integers in binary. Enter a positive integer, switch to binary mode, then press the plus-minus button. It will reveal a twos complement result based on the fixed number of bits being used.
In our next episode, we will discuss another method for representing signed values in binary. This method is not as common as twos complement for representing integers in binary, but an understanding of it will help us when we start using binary to store floating-point values.
For transcripts, links, or other podcast notes, please check us out at intermation.com where you will also find links to our Instagram, Twitter, Facebook, and Pinterest pages. Until then remember that while the scope of what makes a computer is immense, it’s all just ones and zeros.