首页 > 试题广场 >

不用加减乘除做加法

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

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

输入

1,2

输出

3
示例2

输入

0,0

输出

0

不得不吐槽下Python对位操作简直是深坑一座- -

主要原因还是因为python没有无符号又移操作,所以需要越界检查一波~

其他思路和大家是一样的

加法是异或,进位是与<<1

# -*- coding:utf-8 -*- 
class Solution:  
    def Add(self, a, b):            
        while(b):  
           a,b = (a^b) & 0xFFFFFFFF,((a&b)<<1) & 0xFFFFFFFF
        return a if a<=0x7FFFFFFF else ~(a^0xFFFFFFFF)
编辑于 2018-03-05 10:55:25 回复(14)
更多回答
推荐
//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)
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;
    }
}
首先看十进制是如何做的: 5+7=12,三步走
第一步:相加各位的值,不算进位,得到2。
第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。

第三步:重复上述两步,只是相加的值变成上述两步的得到的结果210,得到12。

同样我们可以用三步走的方式计算二进制值相加: 5-1017-111 第一步:相加各位的值,不算进位,得到010,二进制每位相加就相当于各位做异或操作,101^111。

第二步:计算进位值,得到1010,相当于各位做与操作得到101,再向左移一位得到1010(101&111)<<1。

第三步重复上述两步, 各位相加 010^1010=1000,进位值为100=(010&1010)<<1。
     继续重复上述两步:1000^100 = 1100,进位值为0,跳出循环,1100为最终结果。

部门开始招聘实习生,感兴趣的同学可以看看,可以内推
https://www.nowcoder.com/jobs/detail/307599?jobId=307599

编辑于 2024-02-06 18:14:52 回复(97)
class Solution {
public:
    int Add(int num1, int num2)
    {
		char* a = reinterpret_cast<char*>(num1);
        return reinterpret_cast<long>(&(a[num2]));
    }
};

发表于 2016-10-04 15:26:22 回复(9)
//看我的递归版本
class Solution {
public:
    int Add(int num1, int num2)
    {
        if(num2==0)
            return num1;
        return Add(num1^num2, (num1&num2)<<1);
    }
};

发表于 2016-04-30 13:19:20 回复(7)
class Solution {
public:
    int Add(int num1, int num2)
    {
	    //相加各位 + 计算进位
        //十进制思想
        //5+7 各位相加:2 进位:10
        //2+10 12 0
        //12+0
        //二进制计算过程
        //5+7 各位相加:101^111=010 进位:101&111=101 (<<1=1010)
        //2+10 各位相加:010^1010=1000 进位:010&1010=010 <<1=0100
        //8+4 1000^0100=1100 1000&0100=0
        //12+0
        if (num2 == 0) return num1;
        return Add(num1^num2, (num1&num2)<<1 );
    }
};

编辑于 2017-04-19 13:47:43 回复(0)
考虑位运算,分三步:
第一步:不进位加 n1
第二步:计算进位 n2
第三步:n1 和 n2求和(重复第一步,直到进位为0,即n2=0)
在第一步中,采用异或
第二步中,采用按位与,左移一位
public int Add(int num1,int num2) {
        int n1;
        int n2;
        do{
            n1 = num1 ^ num2;
            n2 = (num1 & num2)<<1;
            
            num1 = n1;
            num2 = n2;
        }while(num2 !=0);
        return n1;
    }


编辑于 2015-05-20 15:17:21 回复(0)
class Solution:
    def Add(self, num1, num2):
        # write code here
        if not num1:
            return num2
        elif not num2:
            return num1
        while num2:
            num1,num2 = (num1^num2)&0xFFFFFFFF, (num1&num2)<<1
        
        if num1>>31 ==0:
            return num1 
        else: 
            return  num1 - pow(2,32)
        
首先补充知识,二进制算法是用补码计算的!补码!补码!重要的事情三遍!
首先正数举例,5+6:
bin(5)=0101,bin(6)=0110
首先我们在计算十进制的时候思路是这样的,5+6=11,首先看1,之后发现需要左移也就是所谓的进1,变成11,二进制是类似的;
第一次,0101^0110=0011
                0101&0111=0100,发现0100!=0000,所以是需要进位左移  0100<<1=1000
第二次, 0011^1000=1011
                0011&1000=0000,发现0000==0000,所以返回1011,也就是11
之后负数举例,5-6:(以8位举例)
bin(5)=00000101,bin(-6)=10000110,反码:11111001,补码:11111010
开始计算:
第一次,00000101^11111010=11111111
                00000101&11111010=00000000==00000000,注意11111111是补码,需要转换回去,反码11111110,源码10000001=-1,num1-pow(2,32)作用就是类似,255-256=-1
发表于 2019-06-24 21:56:57 回复(0)

python solution

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        return sum([num1,num2])
发表于 2017-10-07 17:24:21 回复(20)
class Solution {
public:
    int Add(int num1, int num2)
    {
    int result=0;
	__asm__(  
    "add %1,%2\n\t"         //%1表示num2 %2表示num1,这个表示num2的值加到num1上 
    "mov %2,%0\n\t"         //%0表示目的寄存器,把num1复制到result上
    :"=r"(result)           //%0,占用符号  
    :"r"(num2),"r"(num1)  //这一行是将C代码中的数据输入到汇编的代码中  
    );   
      return result;    
    }
};

发表于 2017-01-25 00:24:58 回复(0)
class Solution {
public:
	int Add(int num1, int num2)
	{
		int Sum, Carry;
		do 
		{
			Sum = num2 ^ num1;
			Carry = (num1 & num2) << 1;
			num2 = Carry;
			num1 = Sum;
		} while (num2 != 0);
		return num1;
	}
};

发表于 2015-09-01 11:20:04 回复(1)
function sum(a,b){
   return a ? sum((a&b)<<1,a^b) : b;
}

编辑于 2016-01-15 21:01:47 回复(0)
发表于 2017-05-07 20:35:21 回复(2)
public class Solution {
    public static int Add(int num1, int num2) {
        int sum = 0;
        int carry = 0;
        do {
            // 异或,实现相加但不进位
            sum = num1 ^ num2;
            // 先位与,后左移,相当于进位
            carry = (num1 & num2) << 1;

            num1 = sum;
            num2 = carry;
        } while (num2 != 0);
        return num1;

    }
}


发表于 2015-05-26 22:41:23 回复(1)
import java.math.*;
public class Solution {
    public int Add(int num1,int num2) {
        BigInteger sum1=new BigInteger(String.valueOf(num1));
        BigInteger sum2=new BigInteger(String.valueOf(num2));
        BigInteger res=sum1.add(sum2);
        String a=res.toString();
        int solution=Integer.valueOf(a);
        return solution;
        
    }
}
发表于 2016-06-12 12:31:43 回复(6)
利用位运算代替加法。步骤如下:
【1】不考虑进位。0+0,1+1结果都是0;0+1,1+0结果都是1,也就是异或操作
【2】考虑进位。0+0,0+1,1+0不会产生进位,1+1会向前产生一个进位。因此可以将两个数先做位与运算,再左移一位(0&0,0&1,1&0结果都是0,左移结果不变;1&1结果是1,左移一位10表示向前进一位)
【3】上述两个步骤相加,但是不允许相加操作,所以重复上述过程,直到没有进位。
class Solution:
    def Add(self, num1, num2):
        # write code here
        # 异或、与(与计算考虑进位)之和
        xorNum = num1 ^ num2 # 不考虑进位
        andNum = (num1 & num2)<<1 # 考虑进位
        while andNum!=0: # 若果没有进位的话直接输出结果
            tmp1 = xorNum ^ andNum
            tmp2 = (xorNum & andNum)<<1
            tmp1 = tmp1 & 0xFFFFFFFF # 为了避免负数过大,取前32位
            xorNum = tmp1
            andNum = tmp2
            
        return xorNum if xorNum<=0x7FFFFFFF else ~(xorNum^0xFFFFFFFF)

python 中最后运算结果是按补码进行存储,正数补码是本身,负数补码是该数绝对值的所有位取反再加1。举例来说,如果最后结果是-15,然而不做处理的话xorNum=4294967281(111....110001,15原码或补码为0...01111),该数为-15的补码但是被python认为是一个Long型的长整数。将上述结果与0xFFFFFFFF取异或,可以得到上述数的绝对值15,再取反,得到最后结果。这种操作看似做了个无用操作,但是告诉python解释器这个结果不是长整型,而是被作为负数解释输出。
编辑于 2020-03-16 11:33:44 回复(1)
Java实现,已通过。运行时间:19ms,占用内存:9328k。不能用四则运算,就只能考虑位运算。
两个数相加是这样的:先不考虑进位,将两个数进行无进位相加:1+1=0, 0+0=0, 1+0=1,这是异或运算:int UnsignedSum=num1^ num2; 接下来需要求出进位位,1+1=0时会向前产生一个进位位,而其他情况:0+0  0+1没有进位位,可以想到相与运算,只有1&1=1,其他相与结果都是0,这个1左移1位就能得到所有进位位: signedSum=(num1 & num2 )<<1 (这里一定要带括号,因为<<优先于& )将这个 signedSum继续与UnsignedSum相加,就会重复上述:先是无进位相加,再求进位 ......所以在方法里需要将UnsignedSum赋给num1, 将signedSum赋给num2,直到不产生进位了,signedSum=0为止,代码如下:
public class Solution {
    public int Add(int num1,int num2) {
        //直到不再产生进位
        while (num2!=0)
        {//无进位求和
            int UnsignedSum=num1^num2;
            //求出进位
int signedSum=(num1&num2)<<1;
            num1=UnsignedSum;
num2=signedSum;}
//直到进位num2为0,说明不再产生进位,num1就是最终结果
return num1;

    }
}


也可以写成递归形式:运行时间:16ms,占用内存:9404k
//写成递归形式
    //第一个参数放无进位相加结果,第二个参数放进位位
    //方法:求两个参数的和
    public int Add(int num1,int num2) {
        if(num2==0) return num1;
      return Add(num1^num2,(num1&num2)<<1);
}

2020 二刷
public class Solution {
    public int Add(int num1,int num2) {
if(num2==0) return num1;
      return Add(num1^num2,(num1&num2)<<1);
    }
}

public class Solution {
    public int Add(int num1,int num2) {
while (num2!=0) {
    int UnDigit = num1 ^ num2;
    int Digit = (num1 & num2) << 1;
    num1 = UnDigit;
    num2 = Digit;
}
return num1;
        
        
    }
}
2021 三刷:
public class Solution {
    public int Add(int num1,int num2) {
        while(num2!=0){
        int unsinged=num1 ^ num2;
        int signed=(num1 & num2)<<1;
        num1=unsinged;
        num2=signed;}
        return num1;
    }
}



编辑于 2021-02-10 20:36:33 回复(0)

public class Solution {
    public int Add(int num1,int num2) {
        if (num2==0) 
            return num1;
        return Add(num1^num2, (num1&num2)<<1);
    }
}
  1. 异或运算(^): 如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0
  2. 与运算(&):两位同时为“1”,结果才为“1”,否则为0

1、化简

1. 先看一个例子:
看一下 3 + 4 的加法运算

3 的二进制表示: 011
4 的二进制表示: 100

3^4 (3按位异或4)的结果是: 111 => 7
上面的到的结果是就是 3 + 4 的实际结果


再看一个例子:

12 的二级制表示:  01100
19 的二进制表示:  10011

12^19 的结果是: 11111 => 31

再看一个例子:
13 的二进制表示:01101
19 的二进制表示:10011

13^19 的结果是: 11110 => 20

通过上面的三个例子不难发现: 当二进制数的每一位加法中不发生进位时,按位异或的结果就是最终的加法结果,那么我需要做的就是将所有的加法操作最终都简化成没有进位的加法操作,最终的结果就是两个数按位异或的结果。

2、怎么处理有进位的加法?

拆分
将两个数的加法拆分为 进位加法和不进位加法

看一个例子:


编号:1 2 3 4 5
------------------------
1 0 0 1 1 => 19
+  1 1 0 1 0 => 26
--------------------------

先求只有不进位的两个位相加的值,编号为2、3、5这三位的加法不发生进位操作,需要进位的相加位数直接按照结果为0处理,得到的结果为

编号:1 2 3 4 5

------------------------
1 0 0 1 1
+ 1 1 0 1 0
------------------------
不进位: 0 1 0 0 1

进位两个位相加的值,编号为1、4这三位的加***发生进位操作,不需要进位的直接按照结果0处理,得到的结果为:

编号:1 2 3 4 5
------------------------
1 0 0 1 1
+ 1 1 0 1 0
------------------------
不进位:   0 1 0 0 1
进   位: 1 0 0 1 0 0

再将两个结果按位异或:
不进位:0 0 1 0 0 1
进    位:1 0 0 1 0 0
------------------------
1 0 1 1 0 1 => 45

由此可见可以将一个二进制加法拆分为有进位的位数相加结果 和 无进位的位数相加的结果最终按位异或

3、递归

再看一个例子

编号:1 2 3 4 5
------------------------

1 0 1 1 1 => 23
+ 1 1 0 1 1 => 27
------------------------

不进位:   0 1 1 0 0 => 12
进   位: 1 0 0 1 1 0 => 38


通过一次相加得到的结果不能完全实现化简操作,所以需要递归地进行化简操作

编号:1 2 3 4 5
------------------------

1 0 1 1 1 => 23
+ 1 1 0 1 1 => 27
------------------------

不进位: 0 0 1 1 0 0 => 12
进    位:1 0 0 1 1 0 => 38
------------------------

不进位:1 0 1 0 1 0 => 42
进    位:0 0 1 0 0 0 => 8
------------------------

不进位:1 0 0 0 1 0 => 34
进    位:0 1 0 0 0 0 => 16
------------------------

不进位:1 1 0 0 1 0 => 50
进    位:0 0 0 0 0 0 => 0

以上实例通过递归的方式可以得到最终的结果

二、位运算实现

通过以上几个实例我们明白了如何通过二进制的几个步骤来实现任意整数的加法操作,现在我们需要把这件事情用位运算进行表示。

位运算表示不进位加法:
不进位加法其实就是一个异或操作
位运算表示进位加法:

进位加法其实就是一个与操作的结果左移一位



参考:https://www.cnblogs.com/kingsm/p/9707988.html

编辑于 2019-07-01 20:40:33 回复(0)
public class Solution {
    public int Add(int num1,int num2) {
        int sum=0;
        sum=num1^num2;//异或代表两数相加但不进位,于是 不进位和=真正的和-进位值
        num2=(num1&num2)<<1;//进位值
        sum+=num2;//真正的和=不进位和+进位值
        return sum;
    }
}

发表于 2019-03-04 10:48:07 回复(1)
//模拟按位加法运算
//若当前位有一个或三个1,则为1,否则为0
//若当前位有两个或三个1,则进位
int Add(int num1, int num2)
    {
        int t=1, x=0, ans=0;
        while(t){
            int a = num1&t;
            int b = num2&t;
            ans |= (a^b^x); //有一个或三个1,则当前位为1
            x = ((a&b)|(a&x)|(b&x))<<1; //有一个以上1,进位
            t <<= 1;
        }
        return ans;
    }
发表于 2018-02-14 11:44:41 回复(0)
//递归版本很简单啊
class Solution {
public:
    int Add(int num1, int num2){       
        if((num1&num2)<<1)
            return Add(num1^num2,(num1&num2)<<1);
        else
            return num1^num2;
    }
};

发表于 2017-06-20 17:07:03 回复(0)