Вычесть два числа без использования арифметических операторов

Question

Проблема, с которой я сталкиваюсь: -

Как работает логика побитовых операторов в приведенном ниже коде?

Код:

#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;
}

Как работает функция вычитания (x, y)?

Answer 1

В двоичном коде

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

, то есть

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

Это означает, что

x - y

эквивалентно

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

потому что результат вычитания может быть дан как x ^ y

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

, а сумма заимствования может быть дана как (~x) & y

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

Проверка того, что происходит (положительное и отрицательное) переполнение оставлено на усмотрение пользователя.