不使用算术运算符减去两个数字

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

函数 subtract(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

检查（正和负）溢出时发生的情况留给用户。

Answer 2

使用递归函数

int reduce(int a, int b){
    if(b == 0){
        return a;
    }
    int value, carry;
    carry = ((~a) & b) << 1;
    value = a ^ b;
    return reduce(value,carry);
}

使用 while 循环

int reduce(int a, int b){
    while(b){
        int carry = ((~a) & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

不使用算术运算符减去两个数字

Subtract two numbers without using arithmetic operators

c

bitwise-operators

subtraction