1

I've decided to start learning some logic design recently. I'm current at the very first unit in the book I'm using (Fundamentals of Logic Design - 5th Edition if it's of any importance) and it's given me a series of questions to answer. Prior to the actual question, it gave me the following: A - B = A + (-B). Add the complement of a number with a regular number in place of actually subtracting those numbers directly.

I've gotten to a question where it's asking me to subtract 10110 (22) with 01101 (13) by adding 10110 (22) and the 1's complement of 01101 (10010) together. You'd assume that the answer would be 1001 (9), right? I did just that and did get 01001, but the solutions section of the book I'm using state that there is an overflow. I've even checked another version of the solutions section online, but it's still stated as an overflow. I just want to know why the book stated that this would result in an overflow, but still have the binary representation of the output be correct.

The solution from the book solution section

The solution from the book solution section

I'm still new with this whole logic design stuff. 1's and 2's complement did get me a bit hung up. Help would be appreciated.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
ManedManRicky
  • 13
  • 4
  • What do you mean "stated as an overflow"? Yes, 10110 + 10010 overflows into the sixth bit. Yes, 01001 is the correct result for the subtraction (with an overflow bit set, if you're following such things). What question are you actually asking? – hobbs Aug 28 '22 at 01:45
  • This is for binary subtraction, not subtraction of two signed one's complement numbers? If so, you also need to add with a carry-in of 1 (to make it actually `-B = ~B + 1`, [the 2's complement inverse](https://stackoverflow.com/questions/2278518/how-to-prove-that-the-c-statement-x-x1-and-x-1-yield-the-same-results)). Or if you did really mean rarely used 1's complement math, that's not equivalent to subtracting unsigned binary numbers, and you should tag this [ones-complement]. – Peter Cordes Aug 28 '22 at 14:13
  • a + (-b ) = a + ~b +1 (twos complement invert and add one, ones complement and ADD ONE), invert the second parameter AND the carry in of the lsbit. – old_timer Aug 28 '22 at 14:19

3 Answers3

3

I just want to know why the book stated that this would result in an overflow ...

I can imagine two things:

  1. The book wants you to keep in mind that when using one's complement, you have to add one to the result if there is a carry-out from the highest bit:

    10110 + 10010 = (1)01000 = 01000 + 1

  2. The result is not really correct:

    If you are really calculating with 5-bit numbers (and not with 6-bit numbers), 10110 is not 22 but it is (-9)!

    You need at least 6 bits for the value 22.

    (So the values in the question were already wrong!)

    However, (-9)-13 is (-22) and not 9!

    Because you need at least 6 bits for the value (-22), you cannot get the correct result if you are calculating with 5 bits.

Martin Rosenau
  • 17,897
  • 3
  • 19
  • 38
0

I believe the book is simply trying to state that you have to ignore the overflow when using this method of subtraction, that 01001 is the correct answer and not 101001.

Are you unsure of what 'overflow' means? Can you perhaps try to restate what your actual question is?

William Fleetwood
  • 111
  • 7
  • That may have been what the book was honestly going for. From my understand, an overflow in this context is when a number requires more bits than allowed – ManedManRicky Aug 28 '22 at 02:54
  • Yeah, an overflow is when an operation would result in a number that is larger than the maximum number possible in the given number of bits. An underflow is the opposite, when an operation would result in a number that is smaller than the minimum number possible to represent. In either case, one of two things happen depending on language/environment: 1. Your program crashes (usually preferred) 2. Your number wraps back around becoming either smaller or larger than you expected during overflow or underflow respectively. – William Fleetwood Aug 28 '22 at 02:57
0

They're doing unsigned 5-bit binary, and the result is 5-bit

That's the same binary operation as two's complement, only the interpretation of the values represented by the bit-patterns is different.

22 is 10110, 13 is 01101. We know its unsigned because the leading bit is 1, but it's 22 not -10.

To do 22-13, they're forming ~13 + 1 = 10010 + 1 = 10011 separately in the diagram on the lest, unlike a binary adder-subtractor would. (It would do the +1 as carry-in to a single addition operation1.) The diagram on the right doesn't pre-add the +1.

(That 10011 bit-pattern doesn't necessarily have a meaning as positive or negative number, unless you had zero-extended to at least 6-bit to make the starting numbers all signed-positive. For example, 13-22 would involve 01101 + (01001 + 1).)

Then they add. The carry-out = 1 from addition means there was no borrow. That's why some ISAs like ARM use their carry flag as a not-borrow after subtraction, so they can use that ALU result directly. Instead of inverting it like x86 does so CF=0 means no borrow after cmp or sub, that the subtraction didn't wrap around, because 22U >= 13U.

So it's not correct to call this an overflow in the subtraction. 22 - 13 is mathematically in the 0..31 range, it doesn't need to wrap to stay in that range.

The fact that the add overflowed means that the subtraction didn't. Hopefully that's what the textbook meant or was trying to say.

This can't be 5-bit 2's complement, because the 22 input isn't in the -16..+15 range in the first place. But if you were doing signed 2's complement, signed overflow is a different condition. Unsigned overflow just detects zero-crossing. Unsigned overflow would be something like -9 - 8 which is mathematically -17, in 5-bit 2's complement would wrap to 15. (Overflow in signed subtraction can only happen when the inputs are opposite-sign numbers.)

Footnote 1: it must be a single add-with-carry, not ~y+1 and then add

Note that doing only a single add operation with carry-in is essential for the carry-out to actually be meaningful in all cases. If you did 22 - 0 by first doing 11111 + 1 = 0, then 22 + 0 produce a carry-out of 0. But that's wrong, that would mean that 22U >= 0 is false.

If you do it the way a hardware adder-subtractor would, as 22 + 0b11111 with carry-in of 1, then 22 - 0 does still wrap back to 22, but with carry-out = 1 from the add-with-carry.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847