Concept

What are the representable range and overflow rules for two’s-complement numbers?

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

"One last word on two’s-complement: what is the range of numbers we can represent? It turns out to be -128 to 127. The highest value is 01111111, which is 127. You might think the lowest value would be represented as 11111111, but if you work it out, you’ll find that this is actually the number −1. The lowest number is actually the bit pattern 10000000, which is −128. One last sticky detail we need to cover has to do with overflow. When we add two numbers, there is the possibility that the result will contain one more digit than the original numbers did. You’ve probably seen this on a hand calculator when you press “=” and get an “E” (for “error”) in the display. If there are only ten digits on your display, adding two ten-digit numbers will (sometimes) result in an eleven-digit number that your calculator can’t display, and it’s alerting you to that fact so you don’t misinterpret the result. Here, we might add two 8-bit quantities and end up with a 9-bit quantity that can’t fit in one byte. This situation is called overflow, and we need to detect when it occurs. The rules for detecting overflow are different depending on the scheme. For unsigned numbers, the rule is simple: if a 1 is carried out from the MSB (far left-side), then we have overflow. So if I were to try to add 155₁₀ and 108₁₀: 10011011 + 01101100 = 1 00001111, then I get a carry out left into the 9th digit. Since we can only hold eight digits in our result, we would get a nonsensical answer (15₁₀), which we can detect as bogus because the carry out indicated overflow. Sign-magnitude works the same way, except that I have one fewer bit when I’m adding and storing results. Instead of a byte’s worth of bits representing magnitude, the left-end bit has been reserved for a special purpose: indicating the number’s sign. Therefore, if I add the remaining 7-bit quantities and get a carry out left into the eighth digit, that would indicate overflow. Now with two’s-complement, things are (predictably) not that easy. But it turns out they’re almost as easy. There’s still a simple rule to detect overflow, it’s just a different rule. The rule is: if the carry in to the last (left-most) bit is different than the carry out from the last bit, then we have overflow. Let’s try adding 103₁₀ and 95₁₀ in two’s-complement, two numbers which fit in our -128 to 127 range, but whose sum will not: 01100111 + 01011111 = 11000110. The carry-in to the last bit was 1, but the carry-out was 0, so for two’s-complement this means we detected overflow. It’s a good thing, too, since 11000110 in two’s-complement represents −57₁₀, which is certainly not 103 + 95. Essentially, if the carry-in is not equal to the carry-out, that means we added two positive numbers and came up with a negative number, or that we added two negatives and got a positive. Clearly this is an erroneous result, and the simple comparison tells us that. Just be careful to realize that the rule for detecting overflow depends totally on the particular representation scheme we’re using. A carry-out of 1 always means overflow… in the unsigned scheme. For two’s-complement, we can easily get a carry-out of 1 with no error at all, provided the carry-in is also 1."

Related Ideas

What are the representable range and overflow rules for two’s-complement numbers? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm