Subtract two numbers without using arithmetic operators

Question

The problem that I am facing is :-

How does the logic of bitwise operators are working in the code below?

Code:

#include <stdio.h>

int subtract(int x, int y)
{
    while (y != 0)
    {
        int borrow = (~x) & y;
        x = x ^ y;
        y = borrow << 1;
    }
    return x;
}

int main()
{
    int x = 29, y = 13;
    printf("\nx - y is %d", subtract(x, y));
    return 0;
}

How is the function subtract(x,y) is working?

Answer 1

In binary,

 x   y  | x-y
--- ---   ---
 0   0  |  0
 0   1  |  1 (with a borrow)
 1   0  |  1
 1   1  |  0

which is to say

 x   y  |       x-y
--- ---   ---------------
 0   0  |  0 - ( 0 << 1 )
 0   1  |  1 - ( 1 << 1 )
 1   0  |  1 - ( 0 << 1 )   
 1   1  |  0 - ( 0 << 1 )

That means that

x - y

is equivalent to

( x ^ y ) - ( ( (~x) & y ) << 1 )

because the result of the subtraction can be given by x ^ y

 x   y  | x^y
--- ---   ---
 0   0  |  0
 0   1  |  1
 1   0  |  1
 1   1  |  0

and the amount to borrow can be given by (~x) & y

 x   y  | (~x) & y
--- ---   --------
 0   0  |     0
 0   1  |     1
 1   0  |     0
 1   1  |     0

Checking what happens on (positive and negative) overflow is left to the user.