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 our last episode, we presented an alternate way to represent decimal numbers that eliminated the need for negative signs. If you haven’t listened to that episode, pause this one, and go listen to our Tens Complement Arithmetic episode. It’s okay, we’ll wait, because in that episode, we discuss how a decimal value stored in a fixed number of digits can be used to represent both positive and negative numbers, and how the operation of addition will work even when applied to any combination of signed values. We also discussed how to use the most significant digit as a sign digit instead of as a digit to represent magnitude. 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. Any other numeral means that we were trying to represent a value outside of the allowable range of values for that fixed number of digits.
We also presented an algorithm for switching back and forth between positive and negative values that went something like this. Start by subtracting each decimal digit from nine to determine each new decimal place for the inverse. For example, if we are trying to determine the four-digit additive inverse, or negative, of 873, we subtract each decimal digit from nine to get the four-digit result 9126. The second step is to add one to the inverted pattern of digits, which in our example will give us 9127. Is this the four-digit additive inverse? Well, adding 0873 to 9127 gives us 10,000. But remember, we are limiting ourselves to exactly four digits. This means the carry into the ten to the fourth place is discarded, which gives us the result of zero.
This algorithm to determine the additive inverse of a decimal integer also works in base-2 with one minor adjustment. Instead of subtracting each digit from nine, we subtract each digit from one. In binary, this process is trivial. We just invert or flip each bit. Any bit that’s a one becomes a zero, and any bit that’s a zero becomes a one. This is called a bitwise inverse. The rest of the algorithm is the same, in other words, just add a one to get our final result. In binary, this representation is referred to as twos complement.
Let’s do a quick example to show how the algorithm works in binary. The positive integer 61 broken into its power of two components is 32 + 16 + 8 + 4 + 1, which gives us the 8-bit unsigned binary representation of 61 to be 00111101.
The first step in our algorithm is to take the bitwise inverse of this number. The bitwise inverse of 00111101 is 11000010. Next, add one to the bitwise inverse to get 11000011. That means the twos complement additive inverse of 00111101 is 11000011. Another way of saying this is that -61 in twos complement representation is 11000011. If we add the binary representation of 61, 00111101, to our twos complement representation of -61, 11000011, we get 100000000. But remember, we are only using eight bits, so the carry into the ninth bit is discarded and we get a final result of zero.
Let’s try adding -61 to a positive value. In eight-bit binary, the decimal integer 76 is 01001100. Remember that in twos complement, the algorithm we used is only applied when we want to determine the additive inverse, so the positive integer 76 in twos complement representation is the same as it is in unsigned binary. We also know that 76 will fit easily into eight bits since only seven bits are required to represent the magnitude, which leaves the most significant bit as a zero for its sign. In binary, adding 01001100 to -61’s twos complement representation, 11000011 gives us 100001111. By limiting ourselves to eight bits, the one that was passed into the ninth position is discarded and we get 00001111, which in decimal is fifteen.
As with decimal, the most significant binary digit is no longer used to represent magnitude, rather it is used to represent the sign. A zero in this position identifies a positive integer while a one in this position identifies a negative integer. This bit is also referred to as the sign bit. Let’s take a look at another example.
If we add 56 to -61, we should get a negative result. Fifty-six in 8-bit binary is 00111000. Adding this to our -61 twos complement representation of 11000011 gives us 11111011. Well, that doesn’t look right. But wait, this result has a one in the sign bit position. To determine what this binary pattern represents in decimal, we need to determine its magnitude by computing its binary additive inverse. All that’s left to do is put a negative sign in front of it.
The bitwise inverse of 11111011 is 00000100. Adding one to this gives us 00000101, which is the unsigned binary representation for a decimal five. Therefore, the binary value we started with, 11111011, in twos complement represents decimal negative five, which just so happens to be the result of 56 minus 61.
Unlike tens complement, there is a shortcut to calculating the twos complement of a binary number. This trick can be used if you find the algorithm too cumbersome, or if you’d like to verify the result you got from the first algorithm. Starting from the right most bit and going from right to left, copy consecutive zero bit values until you reach your first binary one. Copy that one too. If the least significant bit is a one, then only copy that first bit. Then invert all the remaining bits.
As an example, let’s compute the 8-bit twos complement additive inverse of 76. Seventy-six in eight-bit binary is 01001100. Since there are two consecutive zeros as the right-most bits of 76, copy those two bits as the two least significant bits of our additive inverse. Also, copy down the one that is immediately to the left of those bits. Therefore, the three least significant bits of our inverse are 100. The remaining bits to the left are to be inverted. These five remaining bits are 01001, which means that the most significant five bits of the twos complement additive inverse of 76 are 10110. That gives us 10110100 as the 8-bit twos complement additive inverse of 76.
In our next episode, we will take a deeper look at how the computer uses twos complement notation in its own integer computations including its use of shifting as a shortcut for multiplication and division and the detection of an overflow.
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.