Concept

How does two’s-complement representation let computers perform subtraction through addition?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"Strange as it sounds, a two’s-complement representation scheme allows us to perform addition and subtraction with a single operation. In first grade (or so), you learned the procedure for adding multi-digit numbers, which we’ve followed several times in this chapter. It involves adding the digits right-to-left and possibly “carrying.” Then in second grade (or so), you learned the procedure for subtracting multi-digit numbers. It involves subtracting the digits right-to-left and possibly “borrowing.” If you’re like me, you found adding easier than subtracting. It’s easy to just carry the one, but to borrow requires looking at the digit to the left, making sure that you can borrow from it (i.e., that it’s not already 0), borrowing from further left until you actually find an available non-zero value, hoping the number on the bottom is actually less than the one on the top (because otherwise you have to switch the order and then add a negative sign to the result), and keeping all of that straight as you march down the line. Even if you didn’t find subtracting more difficult than adding, though, you can’t argue that it’s still a completely different algorithm, with different rules to follow. In computer hardware, we have to implement different circuitry to perform each operation, which is more difficult, costly, error-prone, and power-draining. The wonderful thing about two’s-complement, however, is that with this scheme we actually never need to use the subtraction algorithm. If we want to subtract two numbers — say, 24 − 37 — we can instead take the complement of the second number and then add them. Instead of 24 − 37 we compute 24 + (−37). Let’s see it in action. Using conversion procedures, we can figure out that 24₁₀ is: 00011000 and that positive 37₁₀ is: 00100101. If we wanted to compute 24 + 37, we’d just add these. But instead we’re looking for 24 − 37, so we’ll take the complement of 37 to find −37. Flip all the bits of 37: 11011010 and add one: 11011010 + 1 = 11011011, and so now we’ve determined that in the two’s-complement scheme, −37 is represented by 11011011₂. We’re now ready to compute 24 + (−37): 00011000 + 11011011 = 11110011. So we have our two’s-complement answer, 11110011. What value does that correspond to? Well, the left-most bit is a 1, so it’s a negative number. To find out what it’s the negative of, flip all the bits and add one: 00001100 + 1 = 00001101. This is positive 13, which means the number we inverted to get it — 11110011 — must represent −13. And that is indeed the correct answer, for 24 − 37 = −13."

Related Ideas

How does two’s-complement representation let computers perform subtraction through addition? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm