Binary subtraction

Say I'm going to subtract: 0000 0000 - (-1)

that is: (two complement)

      0000 0000
    - 1111 1111
      ---------
    = ???? ????

Whats gonna happen, my brain is really f***ing with me right now, it went perfectly fine before, I think its the overflow thats screwing me up, can someone g开发者_如何学Pythonive some clearance on this please :)?

Take the two's complement of the subtrahend and add it to the minuend.

  0000 0000
- 1111 1111

 ...

  0000 0000
+ 0000 0001
-----------
  0000 0001

It will be (-11..11). Just like in decimals, the sign is still the sign and (0-x) is still (-x) unless you're using bitwise operation instead of plain subtraction.

You can subtract -1 (binary 1111 1111) by adding its two's complement which is 1 (binary 0000 0001). Thus, in decimal, 0-(-1)=0+1=1 :-)

The way the hardware does it is it inverts the second operand, and performs an add with the carry in on the least significant bit lane to 1. So an add is an add with the carry in being zero and a sub is an add with the operand notted and the carry in set.

You can do it pencil and paper style, where you borrow from the number next to it, but it feels a little goofy compared to decimal numbers. With decimal numbers say 1000 minus 1 the zero on the right becomes a 10, because this is base 10, then the 0 next to it has to borrow as well making it a 10 but then loaning one to the right making it a 9, this continues until your top row is 9 9 10 and you subtract 0 0 1 and get 999. With base 2 0b1000 (which is eight decimal) minus 0b0001, the same thing happens the zero on the right borrows from the left becoming 2 or 0b10 because this is base 2, the zero next to it has to borrow as well becoming a 0b10 then loaning a one to the right making it a 1 and so on so your top row is 1 1 0b10 and the bottom row is 0 0 1 subtract the columns and you get 0b111 or 7 decimal.

So all zeros minus all ones, the top row is 1 1 1 1 1 1 1 0b10 after the first borrow, the bottom row stays as 0 0 0 0 0 0 0 0, subtract the columns and you get 0 0 0 0 0 0 0 1.

My intuition tells me that 0 - (-1) should be equal to 0+1 , or simply 1 .

If you wonder why, try to perform the subtraction bit by bit:

0 - 1          = 10 - 1     = 1, setting borrow to 1.
0 - 1 - borrow = 10 - 1 - 1 = 0, borrow = 1
etc..

And better avoid doing binary subtraction by hand. The idea of 2s complement is to provide a simple way of performing subtraction by adding the reciprocal instead.