Why does the $2$'s and $1$'s complement subtraction works? The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple:

$1.$ Find the $1$'s or $2$'s complement of the subtrahend.
$2.$ Add it with minuend.
$3.$ If there is no carry then then the answer is in it's complement form  we have take the $1$'s or $2$'s
complement of the result and assign a negative sign to the final
answer.
$4.$ If there is a carry then add it to the result in case of $1$'s complement or neglect in case of $2$'s complement.

This is what I was taught in undergraduate, but I never understood why this method work. More generally why does the radix complement or the diminished radix complement subtraction works? I am more interested in understanding the mathematical reasoning behind this algorithm.
 A: To give you the intuition I will focus on non-negative numbers $x,y\ge 0$ and that the numbers are $k$-bit integers.
1-complenet
To get the 1-complement from a number $x$ you flip every bit in $x$s binary representation $\text{bin}(x)$, 1 $\Leftrightarrow$ 0. You can do the same, by subtracting $x$ from the binary number that contains only 1s and is as long as $\text{bin}(x)$. For example,
  111111
 -010111
 -------
  101000

This works for every single bit, and there are no carries, so it works for the whole binary representation.
Thus we can describe the 1-complement of $x$ by $c_1(x):=(2^{k+1}-1)-x$, where $k$ is the number of bits we have per number. By definition of the 1-complement we have $c_1(c_1(x))=x$.
Assume that $x>y$ (rule 4), hence when subtracting, we will have an overflow. Thus we will add $+1$ to the result, which yields
$$ x+c_1(y)+1=x+(2^{k+1}-1)-y+1=(2^{k+1})+(x-y),$$
since we consider only the first $k$ bits, the 1 representing $2^{k+1}$ will vanish, and we get $x-y$.
Assume now that $x\ge y$ (rule 3). Then there is no overflow and 
$$ c_1(x+c_1(y))=c_1 (x+(2^{k+1}-1)-y)=c_1(c_1(y-x))=y-x=|x-y|.$$
2-complement
To get the 2-complement of an number $x$ we flip the bits, starting after the right most 1. This can be interpreted as subtracting $x$ from $2^{k+1}$. Again we look at an example
  1000000
 -0010100
 --------
   101100

Until the first 1 we don't have carries, so the bits are just taken from $x$, after the first 1, we have always a carry, and hence the bits get flipped.
Similarly to the 1-complement let $c_2(x):=2^{k+1}-x$, and again $c_2(c_2(x))=x$. 
Assume that $x>y$ (rule 4), this gives
$$ x+c_2(y)=2^{k+1}-y+x=2^{k+1}+(x-y).$$
Again, the $2^{k+1}$ vanishes since we consider only the first $k$ bits.
Assume that $x<y$ (rule 3), then
$$ c_2(x+c_2(y))=c_2 (x+2^{k+1}-y)=c_2(c_2(y-x))=y-x=|x-y|.$$
Both concepts can be extended (on a very natural way) to work with negative numbers.
A: We consider $k$-bit integers with an extra $k+1$ bit, that is associated with the sign. If the "sign-bit" is 0 then we treat this number as usual as a positive number in binary representation. Otherwise this number is negative (details follow).
Let us start with the 2-complement. To compute the  2-complement of an number $x$ we flip the bits, starting after the right most 1.  Here is an example:
 0010100 -> 1101100

We define for every positive number $a$, the inverse element $-a$ as the 2-complement of $a$. When adding two numbers, we will forget the overflow bit (after the sign bit), if an overflow occurs. This addition with the set of defined positive and negative numbers forms a finite Abelian group. Notice that we have only one zero, which is 00000000. The representation 10000000 does not encode a number. To check the group properties, observe that


*

*$a + (-a) = 0$,

*$a+0=a$,

*$-(-a)=a$,

*$(a+b)=(b+a)$,

*$(a+b)+c= a+ (b+c)$.


As a consequence, we can compute with the 2-complement as with integers. To subtract $a$ from $b$ we compute $a+(-b)$. If we want to restore the absolute value of a negative number we have to take its 2-complement (this explains step 3 in the question's algorithm).
Now the 1-complement. This one is more tricky, because we have two distinct zeros (000000 and 111111). I think it is easiest to consider the 1-complement of $a$ as its 2-complement minus 1. Then we can first reduce the 1-complement to the 2-complement and then argue over the 2-complements.
