LeafLabs Garden

A place to share, learn, and grow...

1. 

   pyrohaz
   Member

   Hey guys,

   This isn't really a question based on the maple, just a question based on digital logic. I was in a lecture earlier this week day dreaming when the lecturer was talking about 2's complement and I thought to myself why overflow mathematics hasn't been thought of? I know that obviously this doesn't allow for numbers below 0 but it seems really easy to implement in logic.

   For example, say you have an 8 bit register and you're currently on 200 yet you want to subtract 40 to say 160, couldnt you surely add 215? Working this out through A-B = C

   A = Number you want
   B = Number you have

   A+(255-B). Obviously where 255 is the MSB number of the bit depth of the system?

   Any ideas?

   Posted 2 years ago #
2. 

   mlundinse
   Member

   First you should add 216 = 256-40 since the overflow subtracts 256.

   Yes this is really the difference between signed and unsigned 8 bit numbers

   The binary representation of unsigned 216 = signed -40 = 11011000'b

   So this can, and it is, used but if used carelessly can add a lot of confusion.
   For instance if you are playing with 8 bit values on a 32 bit machine, can you
   be sure how the compiler/processor handles the overflow ?

   Posted 2 years ago #
3. 

   gbulmer
   Moderator

   pyrohaz - if we work through your proposal:

   A = 200
   B = 40

   result = A - B
   = 200 + (255-40)
   = 200 (1100100) + 215 (11010111)
   = 415 (110011111)
   masked to 8 bits = 10011111 = 159
   which is incorrect.

   The number 215 is suspicious.
   In binary, the bottom binary digit (bit) of a number determines if the number is odd or even.
   Adding or subtracting two even numbers always produces an even number, so 200-40 must be even.
   The operation 255-40 converts an even number to an odd number, so it is either wrong, or there are other steps missing from the algorithm.

   As mlundinse has explained, taking the two's complement, is 256-x, and that does produce the correct binary value.
   Geting the two's complement is straightforward, and does not need the subtraction operation.
   Two's complement: flip all the bits and add one.
   Example 40: (00101000)
   -> flip all the bits (1's complement) = 11010111
   -> add 1 to 11010111 = 11011000 (216)
   Those operations are easy to implement (there must be an add implemented :-)

   An important point which needs reinforcing is, the electronics to do the bit operations on the numbers for signed and unsigned binary addition is the same. The difference is how carry or overflow is interpreted.

   So the nifty part is subtraction is addition using the two's complement of the subtrahend, even for unsigned arithmetic.
   Addition is the same for signed and unsigned numbers, the difference is the interpretation of the carry and top bit (sign) to identify overflow.

   Posted 2 years ago #
4. 

   pyrohaz
   Member

   Oh! I didn't know that was actually how the twos complement is calculated, I knew of the twos complement obviously but thats awesome! There are so many clever engineers in this works, past and present. We've done about binary addition and subtraction through 2's complement (and why signed and offset methods don't work either). I meant 256 in the earlier post come to think of it but thank you for the clarification. Digital electronics is great!

   Posted 2 years ago #

RSS feed for this topic

Reply

You must log in to post.