2's complement example, why not carry?

Question

I'm watching some great lectures from David Malan (here) that is going over binary. He talked about signed/unsigned, 1's compliment, and 2's complement representations. There was an addition done of 4 + (-3) which lined up like this:

0100
1101 (flip 0011 to 1100, then add "1" to the end)
----
0001

But he waved his magical hands and threw away the last carry. I did some wikipedia research bit didn't quite get it, can someone explain to me why that particular carry (in the 8's ->16's columns) was dropped, but he kept the one just prior to it?

Thanks!

Answer 1

At some point you have to set the number of bits to represent the numbers. He chose 4 bits. Any carry into the 5th bit is lost. But that's OK because he decided to represent the number in just 4 bits.

If he decided to use 5 bits to represent the numbers he would have gotten the same result.

Answer 2

The last carry was dropped because it does not fit in the target space. It would be the fifth bit.

If he had carried out the same addition, but with for example 8 bit storage, it would have looked like this:

00000100
11111101
--------
00000001

In this situation we would also be stuck with an "unused" carry.

We have to treat carries this way to make addition with two's compliment work properly, but that's all good, because this is the easiest way of treating carries when you have limited storage. Anyway, we get the correct result, right :)

---

x86-processors store such an additional carry in the carry flag (CF), which is possible to test with certain instructions.

Answer 3

The carry was dropped because there wasn't anything that could be done with it. If it's important to the result, it means that the operation overflowed the range of values that could be stored in the result. In assembler, there's usually an instruction that can test for the carry beyond the end of the result, and you can explicitly deal with it there - for example, carrying it into the next higher part of a multiple precision value.

Answer 4

That's the beauty of it... Your result will be the same size as the terms you are adding. So the fifth bit is thrown out

In 2's complement you use the carry bit to signal if there was an overflow in the last operation.

You must look at the LAST two carry bits to see if there was overflow. In your example, the last two carry bits were 11 meaning that there was no overflow.

If the last two carry bits are 11 or 00 then no overflow occurred. If the last two carry bits are 10 or 01 then there was overflow. That is why he sometimes cared about the carry bit and other times he ignored it.

The first row below is the carry row. The left-most bits in this row are used to determine if there was overflow.

1100
 0100
 1101
 ----
 0001

Answer 5

If you extend the left-hand side by adding more digit positions, you'll see that the carry rolls over into an infinite number of bit positions towards the left, so you never really get a final carry of 1. So the answer is positive.

 ...000100
+...111101
----------
....000001

Answer 6

Looks like you're only using 4 bits, so there is no 16's column.

If you were using more than 4 bits then the -3 representation would be different, and the carry of the math would still be thrown out the end. For example, with 6 bits you'd have:

 000100
 111101
 ------
1000001

and since the carry is outside the bit range of your representation it's gone, and you only have 000001

Answer 7

Consider 25 + 15:

5+5 = 10, we keep the 0 and let the 1 go to the tens-column. Then it's 2 + 1 (+ 1) = 4. Hence the result is 40 :)

It's the same thing with binaries. 0 + 1 = 1, 0 + 0 = 0, 1 + 1 = 10 => send the 1 the 8-column, 0 + 1 ( + 1 ) = 10 => send the 1 to the next column - Here's the overflow and why we just throw the 1 away.

This is why 2's complement is so great. It allows you to add / substract just like you do with base-10, because you (ab)use the fact that the sign-bit is the MSB, which will cascade operations all the way to overflows, when nessecary.

Hope I made myself understood. Quite hard to explan this when english is not you native tongue :)

Answer 8

Because you are talking about 4 bit representations. It's unussual compared to an actual machine, but if we were to take for granted that a computer has 4 bits in each byte for a moment, then we have the following properties: a byte wraps at 15 to -15. Anything outside that range cannot be stored. Besides, what would you do with an extra 5th bit beyond the sign bit anyway?

Now, given that, we can see from everyday math that 4 + (-3) = 1, which is exactly what you got.

Answer 9

When performing 2's complement addition, the only time that a carry indicates a problem is when there's an overflow condition - that can't happen if the 2 operands have a different sign.

If they have the same sign, then the overflow condition is when the sign bit changes from the 2 operands, ie., there's a carry into the most significant bit.

If I remember my computer architecture learnin' this is often detected at the hardware level by a flag that's set when the carry into the most significant bit is different than the carry out of the most significant bit. Which is not the case in your example (there's a carry into the msb as well as out of the msb).

One simple way to think of it is as "the sign not changing". If the carry into the msb is different than the carry out, then the sign has improperly changed.

Answer 10

A carry is not the same as an overflow

In the example you do have a carry out of the MSB. By definition, this carry ends up on the floor. (If there was someplace for it to go, then it would not have been out of the MSB.)

But adding two numbers with different signs cannot overflow. An overflow can only happen when two numbers with the same sign produce a result with a different sign.