首页 > 试题广场 >

不用加减乘除做加法

[编程题]不用加减乘除做加法
  • 热度指数：291236 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

数据范围：两个数都满足
进阶：空间复杂度 ，时间复杂度
示例1

输入

1,2

输出

3
示例2

输入

0,0

输出

0
算法知识视频讲解
查看答案及解析
添加回答
推荐
咩咩jiang头像 咩咩jiang
//step1:按位与是查看两个数哪些二进制位都为1，这些都是进位位，结果需左移一位，表示进位后的结果
//step2:异或是查看两个数哪些二进制位只有一个为1，这些是非进位位，可以直接加、减，结果表示非进位位进行加操作后的结果
//step3:n1&n2是查看有没有进位位了，如果有，需要重复step1、step2；如果没有，保留n1、n2上二进制为1的部分，用或将之合为一个数，即为最后结果
class Solution {
public:
    int Add(int num1, int num2)
    {
        int n1,n2;
        n1=(num1&num2)<<1;
        n2=num1^num2;
        while(n1&n2)
        {
          num1=n1;num2=n2;
          n1=(num1&num2)<<1;
          n2=num1^num2;
        }
        return n1|n2;

    }
};
编辑于 2015-08-18 23:38:52 回复(19)
Java
蓝垫头像 蓝垫
兄弟们可以这样想：
  1. 异或运算 提供两数加和后的二进制非进位信息：

    异或运算的一个关键特性是：当两个比特位不同（即一个为0，另一个为1）时，它返回1；当两个比特位相同（都是0或都是1）时，它返回0。这恰好与不考虑进位的加法相对应：

    • 0 XOR 0 = 0 （0 + 0 = 0，无进位）
    • 1 XOR 0 = 1 （1 + 0 = 1，无进位）
    • 0 XOR 1 = 1 （0 + 1 = 1，无进位）
    • 1 XOR 1 = 0 （1 + 1 = 10，有进位但结果位是0）

    由此可见，异或运算符合不考虑进位的加法操作。

  2. 与运算 提供两数加和后的二进制进位信息：

    与运算则是当两个比特位都是1时才返回1，其余情况下返回0。这与计算进位时的情况相匹配：

    • 0 AND 0 = 0 （0 + 0 没有进位）
    • 1 AND 0 = 0 （1 + 0 没有进位）
    • 0 AND 1 = 0 （0 + 1 没有进位）
    • 1 AND 1 = 1 （1 + 1 有进位）

    由此可见，与运算符合计算进位的操作。但注意，实际进位会发生在更高的比特位上，因此我们需要将与运算的结果左移一位来获得正确的进位。

结合这两个操作，可以通过迭代或递归的方式来实现两数相加。首先使用异或运算得到非进位和，然后使用与运算左移一位得到进位信息。重复这个过程，直到没有更多的进位产生，此时异或运算的结果就是最终的加法结果。

发表于 2024-01-15 18:03:27 回复(0)
Java
拒绝pua的小蜗牛很想潜水头像 拒绝pua的小蜗牛很想潜水
public class Solution {
    public int Add(int num1, int num2) {
        //先与得到进位值，再异或得到非进位值，将进位值左移一位继续与非进位值求和；
        int jres = num1 & num2;
        int res = num1 ^ num2;
        while (jres != 0) {
            jres = jres << 1;
            int temp = jres;
            jres=jres & res;
            res =temp ^ res;
           
        }
        return res;
    }
}
发表于 2023-03-23 21:05:43 回复(0)
Java
BlueProtocol头像 BlueProtocol 
public class Solution {
    public int Add(int num1,int num2) {
        return Integer.sum(num1,num2);
    }
}


发表于 2023-03-22 23:51:37 回复(0)
Java
Greak头像 Greak 
import java.math.BigDecimal;
public class Solution {
    public int Add(int num1,int num2) {
        BigDecimal number = new BigDecimal(num1);
		BigDecimal number2 = new BigDecimal(num2);
		return number.add(number2).intValue();
    }
}

发表于 2022-05-27 17:53:27 回复(0)
Java
YxY201903051225168头像 YxY201903051225168
import java.math.BigDecimal;

public class Solution {
    public int Add(int num1, int num2) {
        BigDecimal n1 = new BigDecimal(num1);
        BigDecimal n2 = new BigDecimal(num2);
        return (n1.add(n2)).toBigInteger().intValueExact();
    }
}
发表于 2022-05-14 20:43:33 回复(0)
Java
来学习的小张头像 来学习的小张 
public class Solution {
    public int Add(int num1,int num2) {
        while(num2 != 0){
            int temp = num1 ^ num2;//两数相加不进位的部分
            num2 = (num1 & num2) << 1;//两数相加，进位的部分
            num1 = temp;
        }
        return num1;
    }
}

发表于 2022-05-07 10:12:34 回复(0)
Java
Monlogue头像 Monlogue 
public class Solution {
    public int Add(int num1,int num2) {
       /*异或：相同为0，不同为1
与：都是1为1
或：都是0为0
以5+7为例  5 ---101 7---111
第一步异或：010
第二步两个数与运算之后左移一位 与的结果0101，左移n位就是删除前面的n，后面补n个0
第三步重复：此时第一个数就是输入的a,b异或的结果，第二数字就是与并左移一位的结果，直到没有进位也就是num2为0
     */
while (num2!=0){
    int temp=num1^num2;//借助temp存放num1异或num2的结果,因为num2要用到没有改变过的num1
    num2=(num1&num2)<<1;
    num1=temp;//可以用5+7理解
}
return  num1; 
    }
}

发表于 2022-01-24 17:01:48 回复(0)
Java
男神20190129221786头像 男神20190129221786 
public class Solution {
    public int Add(int num1,int num2) {
        //异或的本质：无进位相加
        //进位怎么得到？ (a & b) << 1
        int sum = num1;
        while(num2 != 0){//没有进位就停
            sum = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = sum;
        }
        return sum;
    }
}

发表于 2021-09-08 09:32:23 回复(0)
Java
烫杯藕粉头像 烫杯藕粉 
public class Solution {
    public int Add(int num1,int num2) {
        int result;//当前结果
        int ans;//进位
        do{
            result = num1^num2;
            ans = (num1&num2)<<1;
            num1 = result;
            num2 = ans;
        }while(ans!=0);
        return result;            
    }
}
1,异或被称为“半加运算”，即不带进位的加法
 2,当双方的当前位都是1时，才会有进位，可以用与运算得到进位；
(需要左移一位，因为进位就是向左边的数进一)
不断地将进位和当前结果当作加数，继续直到进位为零

发表于 2021-08-11 22:02:41 回复(0)
Java
624huiguorou头像 624huiguorou
/*
    思路：
    使用位运算，实现"+"
    
    1.先计算二进制本位和，就是先不管进位
    分为(0和0 1和1 1和0 0和1四种情况)
    本位相加前两种本位为0，后两张本位为1
    与异或(^)结果相同，所以可以用a^b来算本位和
    
    2.再计算进位和。
    1+1=10等于(1&1)的结果再左移(<<)一位，所以其它也类似。
    所以进位和为(a&b)<<1。
    
    由于进位不只一次，所以用个while循环，直到进位和为0时结束。
    先算本位和然后算进位和，然后把进位和当做本位进行操作。
    
    可以修改num1和num2来做，也可以自己创建变量
*/ 
    public int Add(int num1,int num2) {
        int a= num1,b = num2;
        //用b保存进位，当进位为0时结束（用a保存也一样）
        while(b != 0){
            //计算本位和
            int temp = a ^ b;
            //计算进位和
            b = (a & b) << 1;
            //a保存结果
            a = temp;
        }
        return a;
    }


编辑于 2021-03-31 17:46:13 回复(0)
Java
李臭臭头像 李臭臭
public class Solution {
    public int Add(int num1,int num2) {
        int min = Math.min(num1,num2);
        int i = 0;
        while (i < Math.abs(Math.max(num1,num2))){
            if (Math.max(num1,num2) < 0){
                min--;
            }else{
                min++;
            }
            i++;
        }
        return min;
    }
}
发表于 2021-03-05 23:05:22 回复(0)
Java
yyyyfly头像 yyyyfly 
public class Solution {
    public int Add(int num1,int num2) {
        return Integer.sum(num1,num2);
    }
}
一行代码就搞定了
发表于 2021-02-14 16:28:40 回复(0)
Java
黑尾7头像 黑尾7
public class Solution {
    public int Add(int num1,int num2) {
        int temp = 0;
        while (num2 != 0) {
            temp = num1;
            num1 ^= num2;
            num2 = (temp & num2) << 1;
        }
        return num1;
    }
}
发表于 2020-10-27 14:46:20 回复(0)
Java
牛客89636334号头像 牛客89636334号 
/*例如5+3, 101+011 -> 110+010 -> 100+100 -> 000+1000 -> 1000+0000，
上述加号前者是异或结果，1和0异或得1；后者是位与左移一位结果，1和1位与得1
后者为0结束，此时如果再操作就只能反复得到最终结果1000 */
/*源链接为https://blog.nowcoder.net/n/dcbca76d214744a9a1644ae54a183549?f=comment*/

public int Add(int num1,int num2) {
       while (num2!=0) {
        int temp = num1^num2;
        num2 = (num1&num2)<<1;
        num1 = temp;
      }
      return num1;
    }

发表于 2020-10-10 10:55:16 回复(0)
Java
tornado123头像 tornado123 
    /**
     用三步走的方式计算二进制值相加： 5-101，7-111
     第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
     第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
     第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
     继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
     */
    public int Add(int num1,int num2) {
        int temp;
        while(num2 != 0) {
            // 第一步 计算相加的值，不算进位
            temp = num1 ^ num2;
            // 第二步，计算进位值
            num2 = (num1 & num2) << 1;
            // 为了下一次循环做准备，num1 存储的是 不算进位的值
            num1 = temp;
        }
        return  num1;
    }


发表于 2020-10-03 10:34:29 回复(0)
Java
牛客626904108号头像 牛客626904108号

异或运算

两个值相异结果为真。

1^1=0
0^0=0
1^0=1
0^1=1

与运算

1 & 1 = 1(进位)
1 & 0 = 0(不进位)
0 & 1 = 0(不进位）
0 & 0 = 0(不进位)

在位运算中，我们用“<<”表示向左移动一位，也就是“进位”。

分析：

  1. 两个数异或：相当于每一位相加，而不考虑进位；

  2. 两个数相与，并左移一位：相当于求得进位；

  3. 将上述两步的结果相加，num2=0(进位为0)时跳出循环

public int Add(int num1,int num2) {
    while( num2!=0 ){
        int sum = num1 ^ num2;
        int carray = (num1 & num2) << 1;
        num1 = sum;
        num2 = carray;
    }
    return num1;
}
编辑于 2020-08-29 20:54:11 回复(0)
Java
牛客786118665号头像 牛客786118665号
//因为使用递归是不好的编码习惯,因此递归改为循环
public int Add(int num1,int num2) {
        int x = 0;
        int y = 0;
        while(true){
            x = num1 ^ num2;//获取相加值
            y = num1 & num2;//获取进位
            y = y << 1;//进位的位置左移
            if(y == 0){//没有进位退出,x就是结果
                break;
            }else{
                //把相加值和进位值相加,进入下一个循环, 直到进位为0的时候退出,yes!!!!!!!
                num1 = x;
                num2 = y;
            }
        }
        return x;
    } 
发表于 2020-07-03 22:40:30 回复(0)
Java
晚睡晚起写bug头像 晚睡晚起写bug
A^B：表示不考虑进位的相加；（A&B）<<1：A+B的进位。 
public class Solution {
    public int Add(int num1,int num2) {
        while (num2 != 0) {
            int temp = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }
}

发表于 2020-05-25 22:19:59 回复(0)
提交观点

问题信息

基础数学
难度：
91条回答 115087浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号