binarytwos-complement

Why is it subtracting 1 and doing a bitwise inverse is equivalent to doing a bitwise inverse and adding 1?


I am studying two's complement and have come across 2 methods for converting a number's two's complement representation to its decimal representation:

  1. Subtract 1 from the initial binary number, then do a bitwise inverse. Convert this new binary number to a decimal number and adjust the sign accordingly.

  2. Do a bitwise inverse on the initial binary number, then add 1. Convert this new binary number to a decimal number and adjust the sign accordingly.

Why is it subtracting 1 and doing a bitwise inverse is equivalent to doing a bitwise inverse and adding 1?


Solution

  • TL;DR
    if −a==~a+1, then ~a==−a−1 and ~(a−1)==−(a−1)-1==−a

    Two's complement works by coding a negative number a<0 by 2^n−|a|=2^n+a. This way a+(−a)=2^n and if one ignores bits above n−1 the code of −a has he same mathematical properties for addition as −a.

    So the problem to find two's complement b of a, is to find a number b such as a+b=2^n.
    We can see that binary complement of a, ~a almost has this property.

        a    an-1  an-2    ...  a1    a0
     + ~a   ~an-1 ~an-2    ... ~a1   ~a0
       ---------------------------------
     =          1     1    ...   1     1
    

    Either ai=0 and ~ai=1 or ai=1 and ~ai=0 and a+~a=111..11=2^n−1
    By adding one, we can see that a+~a+1=2^n and that two's complement of a is ~a+1.

    As ~a+1=2^na
    ~a=2^na-1
    If we replace a by (a−1), we get
    ~(a−1)=2^n−(a−1)−1
              = 2^n−a
              = ~a+1

    So ~a+1 and ~(a-1) are identical.