2's complement arithmetic

[Sammyoko]

Please can some distinguish between "overflow" and "carry" when these terms are applied to two's complement arithmetic on 4-bit words.

 

[(*steve*)]

overflow happens when a carry is generated and there's no more bits to stick it into.

 

[Sammyoko]

But does the sign of the operator and the operand determine the ocurrence of a 'carry' or an 'overflow'

 

[Raven Luni]

overflow happens when a carry is generated and there's no more bits to stick it into.

Not quite. It happens when the 2's compliment result of an addition or subtraction has its sign altered due to the size of the register. For example if you have an 8 bit register with 127 (01111111) and you add 1, you'd think the result would be 128 (10000000). Technically it is, but because its 2's compliment, this configuration of bits represents -128, with all subsequent values counting up towards -1 (which would otherwise be 255 or 11111111).

So the overflow is generated when the 2's compliment sign is accidentally switched. It is indepent from the carry and can occur without triggering a carry.

Edit: I see you mentioned 4 bit words so here is a quick reference:

0000: 0
0001: 1
0010: 2
0011: 3
0100: 4
0101: 5
0110: 6
0111: 7
1000: -8
1001: -7
1010: -6
1011: -5
1100: -4
1101: -3
1110: -2
1111: -1

To detect an overflow: Think of a subtraction as the addition of a negative number (this is how it actually works so you only have addition). If the high bit is the same for both operands, and is different from the high bit of the result, then an overflow has occured. If each operand has a different high bit, then you either have a subtraction from a positive (as described) or are adding a positive to a negative number (essentially the same thing). An overflow is impossible in these circumstances. (also note that a subtraction of a positive number from a negative number is the addition of 2 negative numbers, so this is the same as the first case where the high bit is equal for both operands and if different in the result indicates an overflow).

Further note: The treatment of the carry is slightly different for instructions dealing with 2's compliment numbers. For example, Subtract 1 from -1, the result is -2 but if you consider the unsigned equivalent of this operation, you would be adding 15 and 15 to get 30, which is too big for the register and would generate a carry (although the lower 4 bits still represent the -2 correctly). Because you're dealing with 2's compliment, the carry is meaningless and will only be set if you are using an instruction designed for unsigned integers. A 2's compliment add instruction (should) not set the carry in this way. BEWARE of this difference as it is one of the more frustrating pitfalls in low level programming.

P.S. I think I just solved a bug in my Z80 emulator - amazing how writing stuff out focuses the mind

 

[(*steve*)]

Not quite. It happens when the 2's compliment result of an addition or subtraction has its sign altered due to the size of the register. For example if you have an 8 bit register with 127 (01111111) and you add 1, you'd think the result would be 128 (10000000).

A perfect example of generating a carry when there's no more bits to put it into the MSB is a sign bit. When adding +ve numbers, we shouldn't be carrying into it.

A better example is looking at the difference between adding -1 and -127, and -1 and -128. The former does not generate an overflow, but the latter does. In both cases there is carrying involving the sign bit. If you compare this with adding 127 and 1, and 127 and 1, it should become clear what the pattern is.

I don't want to spell it out because I'm pretty sure this is homework.

The main thing though, is that carry happens everywhere (although you might just report it at the end of the word). Overflow is something that involves the MSB only.

 

[Raven Luni]

The main thing though, is that carry happens everywhere (although you might just report it at the end of the word). Overflow is something that involves the MSB only.

A good illustration of the difference between a SE and an EE. When we consider terms like carry, overflow etc we think of a CPU's FLAGS register and how it is set at the end of an instruction, rather than considering whats going on with the individual adders etc

P.S. The MSB is only a sign bit for the duration of an instruction designed for signed arithmetic.