What is the purpose of overflow bits in binary arithmetic?

[maiad]

i'm not really understanding 2'compliment. Let's say your using 5 bit signed system and the binary number 00101 represents the decimal number 5. when i do twos complement, the binary number will be 11011. I know the left most digit is used to represent the sign but how are the rest (1011) also equal to 5? isn't it equal to 11?

 

[Bill Simpson]

...
5 00101
4 00100
3 00011
2 00010
1 00001
0 00000
-1 11111
-2 11110
-3 11101
-4 11100
-5 11011
...

Just look at the bit pattern as you decrement by one in each row.
(Please check this very carefully, I hope I still remember this correctly)

http://en.wikipedia.org/wiki/Two's_complement

 

[jim hardy]

Malad I hope this helps - it helped me..

The binary system is cyclic just as is your car's odometer(if it's mechanical).

Observe if you start a six digit counter at zero and continuously increment it,
(I'll separate the MSB so it resembles Bill's count)

when it reaches 0 11111, which is 31
the next increment will push it to 1 0000 which is 32.
Next increment pushes it to 1 00001 , 33

Keep on counting until you reach 1 11111 , 63
next increment takes us back to 0 00000 , zero (and presumably sends a carry off someplace)

But wait a minute - MSB is the sign bit ! We flipped it at 32!

SO what have we here - we got into negative numbers by repetitive adding? Hmmm, That's counterintuitive...

So work it the other way 'round for a sanity check - start at zero and decrement -
1 11111 = -1
halfway around we flip the MSB and get back into positive territory...
Well at least it's consistently counterintuitive.
......

We have chosen to use this cyclic machine for representing numbers,
Arbitrarily assigning to half of it negative numbers and to the other half of it positive numbers...

so the starting point must be arbitrary as well , we could have really screwed things up by assigning value zero to the bitstring a quarter of the way around from 0 0000...

So I hereby assert:

Negative numbers exist only in the mind of the programmer.

two's complement is a mental trick that I figured was no longer necessary once I accepted 'negative or positive' is just an arbitrary agreement among programmers..
the system itself is cyclic and predictable.

If this only confuses things further, disregard.

old jim

 

[rbj]

"Negative numbers exist only in the mind of the programmer."

two's complement is a mental trick that I figured was no longer necessary once I accepted 'negative or positive' is just an arbitrary agreement among programmers..
the system itself is cyclic and predictable.

jim, i think you're perspective is fine. it's cyclical, like an odometer (in fact, the old 6800 and some other 8-bit microprocessors had a base-10 BCD addition function, and to do subtraction, they talked of the "9's complement").

anyway, let's say that $W$ is the word width in bits. for an unsigned $W$-bit number, the range of possible values is

$$0 \le N \le 2^W - 1$$

the biggest unsigned value the $W$-bit word can handle is $2^W-1$. and the bit pattern for that biggest value is all 1's (as it has to be for an unsigned number):

$$2^W - 1 = \underbrace{ 111 \cdots 11 }_{W}$$

the point of overflow (where it "wraps around" or where this binary "odometer" turns over) is between $2^W-1$ and $0$.

so, as far as addition is concerned, your quote is right: "Negative numbers exist only in the mind of the programmer."

with this $W$-bit word, what bit pattern would you have so that if you add 1 to that word you get 0? the answer is $2^W-1$.

so then change the role of that bit pattern in your mind: what number or value would you have so that if you add 1 to that number you get 0? and that answer is, of course, -1.

so that bit pattern, 111...11, can take the role of -1 because when you add 1 to it, you get 0.

now if -1 was the only negative number you needed, you could just bump the point of overflow from between $2^W-1$ and $0$ to between $2^W-2$ and $-1$ (the latter has the same bit pattern as $2^W-1$). but we generally think we need more negative numbers than just -1. so, both as a matter of convention, but also as a matter of simplicity, in this circle of $2^W$ bit patterns, they moved the point of overflow from between $2^W-1$ and $0$ (or between 111..11 and 000..00) to between $2^{W-1}-1$ and $-2^{W-1}$ (or between 011..11 and 100..00). the latter is the same bit pattern for $2^{W-1}$ for an unsigned $W$-bit word. they moved the boundary for where overflow occurs in this circle of bit patterns to exactly the opposite side of the circle. that's all two's-complement is.

now, can you see what the reason that the two's-complement is the same as the simple one's complement with 1 added? the reason is this:

$$-N \ = \ (-1 \ - \ N) + 1$$

think about, with how these cyclical two's-complement numbers are derived above, and how the bit pattern of all ones, 111..11, always corresponds to the value -1. then think about what it is like to subtract N from -1. are there any borrow operations between bits? that means that the one's-complement (the same as N, but with all of the bits inverted; 0 becomes 1 and 1 becomes 0) is the same as $(-1 \ - \ N)$. then to get $-N$ all you need to do is add 1.

 

[rcgldr]

The advantage of 2's complement is that an add or subtract operation can perform the math as if the numbers were unsigned. The only difference is the setting of the overflow bit in case the numbers were signed and overflow occurred.

A bit off topic, but since it was mentioned:

The old 6800 and some other 8-bit microprocessors had a base-10 BCD addition function.

So do the Intel X86 chip series (PC's), DAA (decimal adjust after addition), DAS (decimal adjust after subtraction). Most businsess oriented mainframes also support BCD because decimal math is required for banking and other forms of accounting math in many countries (to avoid issues with binary <-> decimal conversion). Packed decimal is a variable type in Cobol.

 

[jim hardy]

Thanks rbj and rcg..

I'm not a computer guy so maybe shouldn't have jumped into your forum
but the question I thought needed a basic answer...

your eloquent explanation has validated my simple memory aid, derived empirically:
"To negate flip all the bits and add one."

And it makes perfect sense to have the MSB toggle point opposite zero, even if it is only for the beauty of symmetry. I appreciate your point about representing same number of negative and positive numbers.

Thank you for all that work - I'm struggling with Latex yet.

My confidence is boosted now.
...
I've heard of BCD operations in hardware but never encountered such a machine...

If you hear of an instruction set that includes "Convert to Roman Numerals Modulo60" please let me know - I'm working on a clock !

old jim

 

[rbj]

The advantage of 2's complement is that an add or subtract operation can perform the math as if the numbers were unsigned. The only difference is the setting of the overflow bit in case the numbers were signed and overflow occurred.

yup. i was trying to reinforce jim's statement that (at least for addition/subtraction) whether the number is negative or positive is in the programmers head. the adder does not care. but this is not the case for a multiplier. then, whether the bit pattern is for a positive or negative value does matter to the hardware and it is not just a concept in the mind of the programmer.

A bit off topic, but since it was mentioned:

i was just trying to point out the similarity of the one's complement for binary numbers to the nine's complement for base-10. just like the one's complement is like subtracting a positive value from 111...11 in base-2, the nine's complement is like subtracting a positive value from 999...99 in base-10. in either case, there is no borrowing done. and you add one to the result to get the negative.

 

[rcgldr]

I was just trying to point out the similarity of the one's complement for binary numbers to the nine's complement for base-10. just like the one's complement is like subtracting a positive value from 111...11 in base-2, the nine's complement is like subtracting a positive value from 999...99 in base-10. in either case, there is no borrowing done. and you add one to the result to get the negative.

There's also some extra overhead. For example, if adding a pair of 1's complement numbers, if there's a carry, you need to increment the result.

 

[rbj]

There's also some extra overhead. For example, if adding a pair of 1's complement numbers, if there's a carry, you need to increment the result.

well, i don't know why one just adds a pair of one's-complement numbers.

the 1's-comp is *almost* the binary negative (but you have to add 1 to make it precisely the negative). when subtracting B from A, that is the same as adding the negative of B to A, and that is the same as adding the one's-complement of B to A, but you have to add 1 just as you would to get the true negative (which is the 2's comp).

now, in fixed-point signal processing using general purpose CPUs, i have seen this trick to simply approximate the negative of a binary value with its one's complement. so it will be off by 1 in the LSB. what is gained is that you don't have to worry about the case of negating 0x8000 (let's say it's a 16-bit fixed point) and either being way off or having to put in code to test for that possibility. adding this test (and saturate) code worsens the worst-case execution time.

 

[rbj]

The advantage of 2's complement is that an add or subtract operation can perform the math as if the numbers were unsigned. The only difference is the setting of the overflow bit in case the numbers were signed and overflow occurred.

the issue is which overflow bit is set. on some (smart) processors, there are two different overflow bits.

the other thing that i was going to mention is that i believe the Motorola convention for these four bits in the Condition Code Register (sometimes called the Status Register) got it nearly perfectly correct: V N Z C

i think, for simplicity, they did the carry bit, C, backwards for SUB and SUBC (subrtract with carry) instructions. the carry bit should be set if no borrow happens and should be clear if a borrow occurs. a borrow in subtraction is the opposite of carry when the bits of the value being subtracted is the one's complement. the old 6502 did this correctly and simply (except you needed to set or clear the carry bit for the first add or subtract because they only had ADC and SBC instructions, that was not good). so in hardware, if it's a subtract instruction, all you need to do is invert the bits of the operand being subtracted (using XOR gates) and the same "1" that goes into the XOR gates to invert the operand bit, that "1" goes into the carry-in of the LSB one-bit full adder. if it's ADD, a 0 goes into the XOR gates (so they do not invert the bits) and into the carry-in of the LSB adder. in the Mot 6800, for the SUB and SUBC instructions, they had to change the meaning of the C bit going into the CCR and change it back to the natural definition coming out (but only for the subtraction instructions).

but the use of the oVerflow bit, V, is there to detect if it crosses the two's-complement overflow boundary between 0x7FFF and 0x8000 (if they were 16-bit numbers). it doesn't matter which direction. so, if you are performing a long, multi-word addition or subtraction, you start out with the least-significant byte or word with ADD or SUB (no carry), repeat with ADC or SBC going all the way up to the most-significant word. and then test the V bit for overflow only after the final addition or subtraction. the state of the V bit does not matter on the way up, but only at the final value.

the N and Z bits were simple. the N bit was the same as the MSB of the result and the Z bit was set only if all of the bits of the result are 0.

 

[rcgldr]

I don't know why one just adds a pair of one's-complement numbers.

Some older computers, like CDC 3000 series, used 1's complement math.

On some (smart) processors, there are two different overflow bits.

I'm not aware of any. Typically there is a carry bit (carry for add, borrow for subtract), and an overflow bit for signed add, signed subtract, signed or unsigned multiply (if product too large to fit in output), signed or unsigned divide (if quotient too large to fit in output or divide by zero).

I think, for simplicity, they did the carry bit, C, backwards for SUB and SUBC (subrtract with carry) instructions.

Motorola 68000 series uses the X bit, which is normally set the same as the carry bit, to mean carry for add, borrow for subract. Instruction names are ADD, ADDX, SUB, SUBX. Intel X86 series just uses carry bit to mean carry or borrow, and instruction names are ADD, ADC, SUB, SBB.

 

[rbj]

Some older computers, like CDC 3000 series, used 1's complement math.

i will admit i know very little about big old computers, like the 360 or 370 or VAX or PDP-whatever. i know something about the old microprocessors before they could even multiply by an instruction.

the issue is which overflow bit is set. on some (smart) processors, there are two different overflow bits.

I'm not aware of any.

oh c'mon. C bit for overflow using unsigned binary arithmetic and V bit for overflow using signed binary arithmetic.

Typically there is a carry bit (carry for add, borrow for subtract),

but is borrow-not in the 6502 and it's actually simpler conceptually to be that.

and an overflow bit for signed add, signed subtract, signed or unsigned multiply (if product too large to fit in output),

for multiply, what would that mean, that the most-significant word of the result is not zero (for unsigned multiply) or a sign extension of the MSB of the low word?

signed or unsigned divide (if quotient too large to fit in output or divide by zero).

anyway, i was trying to keep the pedagogy at very early and simple microprocessor (pre-multiply and pre-divide instruction, you had to do those with a subroutine) just to illustrate how basic this two's complement is. you have one boundary between 111..11 and 000..00 to indicate an overflow for unsigned numbers and arithmetic and you have another boundary at the opposite side of the circle between 011..11 and 100..00 to indicate an overflow for signed arithmetic. but it's the same ADD and SUB instructions whether you do unsigned or signed. you propagate the carry bit up to higher order words exactly the same whether its signed arithmetic or not. the only difference, at the end of the addition or subtraction operation is which overflow bit is checked to deal with such.

Motorola 68000 series uses the X bit, which is normally set the same as the carry bit, to mean carry for add, borrow for subract. Instruction names are ADD, ADDX, SUB, SUBX. Intel X86 series just uses carry bit to mean carry or borrow, and instruction names are ADD, ADC, SUB, SBB.

i remember that. i never really saw a basic logical need for the X bit. they used it also for rotate, the arithmetic and logical shifts. i never really understood the need for that. i would have just used the carry bit and saved on the number of conditional branches.

 

[rcgldr]

i will admit i know very little about big old computers, like the 360 or 370 or VAX or PDP-whatever.

Even for the old computer's, 1's complement was somewhat rare.

2 overflow bits?

C bit for overflow using unsigned binary arithmetic and V bit for overflow using signed binary arithmetic.

Most computers have a carry bit and an overflow bit, so I thought you meant a second overflow bit that wasn't the carry bit, similar to the 68000 series which has two "carry" bits, C and X (some math instructions set both C and X bits, while other instructions, like CMP, don't set the X bit).

overflow on multiply

for multiply, what would that mean?

Some multiply instructions use a single register for output instead of a double register. For the Intel X86, the signed multiply, IMUL, has variations where a single output register is specified (instead of the usual implied ?DX:?AX register pair), and in that case overflow can occur.