两个数字相加，不带 +运算符（澄清）

发布于 2025-01-01 04:38:43 字数 352 浏览 0 评论 0原文

我知道我们可以使用二进制加法器的逻辑，其中 Sum = a XOR b 和 Carry = a AND b

我也得到了一个解决方案：

int add(int a, int b)
{
     if(b == 0)
         return sum;
     sum = a ^ b;
     carry = (a & b) << 1;
     return add(sum,carry);
}

我不明白这就是为什么在每次递归期间进位会移位或乘以 2？

原文

I know that we can use the logic of binary adder where Sum = a XOR b and Carry = a AND b

I have also got a solution:

int add(int a, int b)
{
     if(b == 0)
         return sum;
     sum = a ^ b;
     carry = (a & b) << 1;
     return add(sum,carry);
}

What I don't understand here is why is the carry bit shifted, or multiplied by 2 during each recursion?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

自在安然 2025-01-08 04:38:43

我发现这有点难以解释，但这是一种尝试；一点点加起来，只有4种情况；

0+0=0 
0+1=1 
1+0=1 
1+1=0 (and generates carry)

这两行处理不同的情况

sum = a ^ b

处理情况 0+1 和 1+0，sum 将包含简单情况，所有加起来为 1 的位位置。

carry = (a & b) << 1

(a & b) 部分查找情况 1+1 的所有位位置。由于加法结果为 0，因此进位很重要，它会移到左边的下一个位置 (<<1)。需要将进位添加到该位置，因此算法再次运行。

重复该算法直到不再有进位，在这种情况下 sum 将包含正确的结果。

顺便说一句，return sum 应该是 return a，那么 sum 和 carry 都可以是常规局部变量。

I find this a bit tricky to explain, but here's an attempt; think bit by bit addition, there are only 4 cases;

0+0=0 
0+1=1 
1+0=1 
1+1=0 (and generates carry)

The two lines handle different cases

sum = a ^ b

Handles case 0+1 and 1+0, sum will contain the simple case, all bit positions that add up to 1.

carry = (a & b) << 1

The (a & b) part finds all bit positions with the case 1+1. Since the addition results in 0, it's the carry that's important, and it's shifted to the next position to the left (<<1). The carry needs to be added to that position, so the algorithm runs again.

The algorithm repeats until there are no more carries, in which case sum will contain the correct result.

Btw, return sum should be return a, then both sum and carry could be regular local variables.

回复收藏 0 原文

┼── 2025-01-08 04:38:43

public class AddSub {

    int sum=0,carry=0;
    public static void main(String[] args) {
        System.out.println("Add "+new AddSub().addition(93,5));
        System.out.println("Sub "+new AddSub().subtraction(7,60));
        System.out.println("Sub "+new AddSub().multiplication(9,60));
    }

    public int addition(int a, int b)
    {
        if(b==0)
        {
            return a;
        }
        else
        {
             sum = a^b;
             carry = (a&b)<<1;
            return addition(sum,carry);         
        }
    }

    public int subtraction(int a, int b){

        return addition(a,addition(~b,1));

    }

    public int multiplication(int a, int b){       
        for(int i=0;i<b/2;i++)
            sum = addition(sum,addition(a,a));
        return sum;     
    }
}

public class AddSub {

    int sum=0,carry=0;
    public static void main(String[] args) {
        System.out.println("Add "+new AddSub().addition(93,5));
        System.out.println("Sub "+new AddSub().subtraction(7,60));
        System.out.println("Sub "+new AddSub().multiplication(9,60));
    }

    public int addition(int a, int b)
    {
        if(b==0)
        {
            return a;
        }
        else
        {
             sum = a^b;
             carry = (a&b)<<1;
            return addition(sum,carry);         
        }
    }

    public int subtraction(int a, int b){

        return addition(a,addition(~b,1));

    }

    public int multiplication(int a, int b){       
        for(int i=0;i<b/2;i++)
            sum = addition(sum,addition(a,a));
        return sum;     
    }
}

回复收藏 0 原文