2

I'm trying to wrap my head around overflow within twos complement for example say I'm trying to take away these two binary numbers: 1111 1000 0100 - 010 111 001 000

I convert the 2nd binary number to it's two complement equivalent and then simply add it but I noticed it resulted in an overflow of 1, do I simply ignore the overflow? or is there a rule I must follow 1111 1000 0100 + 1010 0011 1000 = (1) 1001 1011 1100

Wolf
  • 311
  • 1
  • 3
  • 12

3 Answers3

3

Short answer:

if you are performing arithmetic on fixed-width binary numbers, using two's complement representation for negative numbers, then yes, you ignore the one-bit overflow.

Long Answer:

You can consider each ith bit in n-bit two's complement notation have place value 2^i, for 0 <= i < n - 1, with bit n - 1 (the sign bit) having place value -2^(n - 1). That's a negative place value for the sign bit. If you compute the sum of two such numbers as if they were unsigned n-bit binary numbers, these cases are fine:

  • the sign bit is not set in the either addend or in the result (reinterpreted as being in two's-complement representation),
  • the sign bit is set in exactly one of the addends, regardless of overflow (which is ignored if it occurs), or
  • the sign bit is set in both addends (therefore there is an overflow, which is ignored) and in the result.

To understand that, it may be easier to think about the problem as two separate sums: a sum of the sign bits, and a sum of the value (other) bits. An overflow of the value sum yields an overflow bit whose place value is 2^(n-1) -- exactly the inverse of the place value of a sign bit -- therefore such an overflow cancels one sign bit.

The negative + negative case requires such a cancellation for the result to be representable (two sign bits + one value overflow = one sign bit), and the positive + positive case cannot accommodate such a cancellation because there is no sign bit available to be cancelled. In the positive + negative case, there is an overflow of the value-bit sum in exactly those cases where the result is non-negative; you can consider that to cancel the sign bit of the negative addend, wich yields the same result as ignoring the overflow of the overall unsigned sum, and reinterpreting the sum as a two's complement number.

The remaining cases yield mathematical results that cannot be represented in n-bit two's complement format -- either greater than the largest representable number, or less than the smallest. If you ignore overflow then such results can be recognized by an apparent sign flip. What you do with that is a question of error recovery strategy.

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
0

From Wikipedia's article on 2's complement in the section on addition at https://en.wikipedia.org/wiki/Two%27s_complement#Addition, my understanding is that carry beyond the given (fixed) bit length (to the left) can be ignored but not overflow as determined when the leftmost two bits of the carry are different. The article shows how to maintain a carry row so as to tell if there was overflow and here is a simple example in the same style:

In 4 bit 2's complement -2 is 1110 and +3 is 0011 so

11110  carry 
 1110  -2
+0011  +3
 ----
10001  which is 0001 or simply 1 ignoring the carry in bit 5 and is 
       safe since the leftmost two bits in the carry row are identical
0

Although this is a very old question, it comes up frequently. In two's complement addition, a carry out from the leftmost digit is discarded. Why? Although not precisely correct mathematically, it is easiest to think of a two’s complement number as having a sign bit on the left and value bits elsewhere. The only way a carry out of the sign bit can occur is if the sign bits of both addends were one (negative) and there was a carry in to the sign bit. In that case, the sign bit of the result will be one, which is correct. A problem occurs if the carry in to the sign bit is different from the carry out. That causes an incorrect sign bit, which is an overflow condition. That can be detected without referring to the carry out from the sign bit because the sign of the result will be wrong. For example, if two positive numbers are added and the result is negative, something is wrong. The something that’s wrong is that the sum of the value bits has overflowed into the sign bit and the result is in error.

With pen and paper arithmetic, it is usual to discard the carry and check that the sign of the result is correct. In electronic circuits, the easiest way is to compare that carry in to the carry out with an XOR and signal an error if they differ. The carry out is not otherwise used or stored.

Bob Brown
  • 1,463
  • 1
  • 12
  • 25