Carry Bit, Overflow Bit and Signed Integers

It has already been explained how the Carry Bit works for addition. Now there was interest in a comment about how it would work for negative numbers.

The point is, that the calculation of the carry bit does not have any dependency on the sign. The nature of the carry bit is that it is meant to be used for the less significant parts of the addition. So assuming we add two numbers $x$ and $y$ that are having $k$ and $l$ words, respectively. We assume that $n=\max(k,l)$ and make sure that $x$ and $y$ are both $n$ words long by just providing the necessary number of 0-words in the most significant positions. Now the addition is performed as described by starting with a carry bit of 0 and adding with carry $x[0]+y[0]$ , then $x[1]+y[1]$ and so on up to $x[n-1]+y[n-1]$ , assuming that $x[0]$ is the least significant word and $x[n-1]$ the most significant word, respectively. Each addition includes the carry bit from the previous addition. Up to this point, it does not make any difference, if the numbers are signed or not.

Now for the last addition, we need to consider the question, if our result still fits in $n$ words or if we need one more word. In the case of unsigned numbers we just look at the last carry bit. If it is 1, we just add one more word in the most significant position with the value of $1$ , otherwise we are already done with $n$ words.

In case of signed integers, we should investigate what can possibly happen. The input for the last step is two signed words and possibly a carry bit from the previous addition. Assuming we have $m$ -Bit-words, we are adding numbers between $-2^{m-1}$ and $2^{m-1}-1$ plus an optional carry bit $c$ . If the numbers have different signs, actually an overflow cannot occur and we can be sure that the final result fits in at most $n$ words.

If both are not-negative, the most significant bits of $x[n-1]$ and $y[n-1]$ are both $0$ . An overflow is happening, if and only if the sum $x[n-1]+y[n-1]+c \ge 2^{n-1}$ , which means that the result „looks negative“, although both summands were not-negative. In this case another word with value 0 has to be provided for the most significant position $n$ to express that the result is $\ge 0$ while maintaining its already correctly calculated result. It cannot happen that real non-zero bits are going into this new most significant word. Consequently the carry bit can never become 1 in this last addition step.

If both are negative, the most significant bits of $x[n-1]$ and $y[n-1]$ are both $1$ . An overflow is happening, if and only if the sum $x[n-1]+y[n-1]+c \lt 2^{n-1}$ , which means that the result „looks positive or 0“, although both summands were negative. In this case another word with value $2^n-1$ or $-1$ , depending on the viewpoint, has to be prepended as new most significant word. In this case of two negative summands the carry bit is always 1.

Now typical microprocessors provide an overflow flag (called „O“ or more often „V“) to deal with this. So the final addition can be left as it is in $n$ words, if the overflow bit is 0. If it is 1, we have to signal an overflow or we can just provided one more word. Depending on the carry flag it is $0$ for C=0 or all bits 1 ( $2^n-1$ or $-1$ , depending on the view point) for C=1.

The overflow flag can be calculated by $o := \mathrm{signbit}(x) = \mathrm{signbit}(y) \land \mathrm{signbit}(x+y\mod 2^n) \ne \mathrm{signbit}(x)$ .
There are other ways, but they lead to the same results with approximately the same or more effort.

The following table shows the possible combinations and examples for 8-Bit arithmetic and $n=1$ :

x<0 or x≥0	y<0 or y≥ 0	(x+y)%2^8 < 0 or ≥ 0	Overflow Bit	Carry Bit	additional word needed	value additional word	Examples (8bit)
x≥0	y≥0	≥0	0	0	no	-	0+0 63+64
x≥0	y≥0	<0	1	0	yes	0	64+64 127+127
x≥0	y<0	≥0	0	0 or 1	no	-	65+(-1) 127+(-127)
x≥0	y<0	<0	0	0 or 1	no	-	7+(-8) 127+(-128) 0+(-128)
x<0	y≥0	≥0	0	0 or 1	no	-	-9 + 12 -1 + 127 -127+127
x<0	y≥0	<0	0	0 or 1	no	-	-128+127 -128+0 -1 + 0
x<0	y<0	≥0	1	1	yes	-1	-64 + (-65) -128+(-128)
x<0	y<0	<0	0	1	no	-	-1 + (-1) -1 + (-127) -64 + (-64)

If you like, you can try out examples that include the carry bit and see that the concepts still work out as described.

Carry Bit, Overflow Bit and Signed Integers

Links

Beteilige dich an der Unterhaltung

Schreibe einen Kommentar

Antworten abbrechen