mathbinarytwos-complementnegative-numberinternal-representation

Subtraction of 2 negative integer (two's complement) never overflowing


I came across this in a computer architecture textbook:

Subtracting a strictly negative integer from another strictly negative integer (in two's complement) will never overflow.

The textbook doesn't go on to explain this assertion. It piqued my curiosity.

Why is this statement true?


Solution

  • Here's how it works for 32 bit integers. It works the same for any other bit length.

    The largest negative number is -1.

    The smallest negative number is -2^31.

    Overflow occurs if a result is greater than or equal to 2^31, or smaller than -2^31.

    You get the largest result of a subtraction by subtracting the smallest number from the largest one. -1 - (-2^31) = 2^31 - 1. This is small enough.

    You get the smallest result of a subtraction by subtracting the largest number from the smallest one. -2^31 - (-1) = -(2^31 - 1). This is greater than -2^31.