首页 > 试题广场 >

不用加减乘除做加法

[编程题]不用加减乘除做加法
  • 热度指数：291228 时间限制：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)
Python
tantantansq头像 tantantansq 
class Solution:
    def Add(self, num1, num2):
        # write code here
        x=0xffffffff
        n1, n2 =num1&x, num2&x #负数变补码，正数不变
        while n2:
            n1,n2=n1^n2, (n1&n2)<<1 &x 
        return n1 if n1<=0x7fffffff else ~(n1^x)

发表于 2021-08-05 13:01:30 回复(0)
Python
浮狸头像 浮狸 
class Solution:
    def Add(self, num1, num2):
        # write code here
        xornum = num1 ^ num2
        andnum = (num1 & num2) << 1
        while andnum:
            temp1 = xornum ^ andnum
            temp2 = (xornum & andnum) << 1
            temp1 = temp1 & 0xFFFFFFFF
            xornum = temp1
            andnum = temp2
        return xornum if xornum <= 0x7FFFFFFF else xornum - 0x100000000

发表于 2021-06-17 00:20:53 回复(0)
Python
RD_Harry头像 RD_Harry 

	我这错在哪呀，可以运行的呀




def Add( num1, num2):
        # write code here
        num1 = int(num1)
        num2 = int(num2)
        num3=sum((num1,num2))
        print(num3)

if __name__ == '__main__':
    num1=input("第一个数:")
    num2=input("第二个数:")
    Add(num1,num2)
发表于 2020-09-21 13:09:43 回复(0)
Python
DDooo头像 DDooo
方1：利用sum()函数： 
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        return sum([num1,num2])
   
需要注意的是，sum函数调用的格式：sum(iterable[, start]),也就是说sum()最后求得的值 = 可迭代对象里面的数加起来的总和(字典:key值相加) + start的值(如果没写start的值，则默认为0)。

方2：利用列表append()和sum()函数： 
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        s = []
        s.append(num1)
        s.append(num2)
        return sum(s)



发表于 2020-07-22 16:05:44 回复(0)
Python
牛客624277366号头像 牛客624277366号 
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        return sum([num1, num2])

发表于 2020-05-28 14:46:20 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa 
# -*- coding:utf-8 -*-
class Solution:
   
            
    def Add(self, num1, num2):
        a=num1
        b=num2
        a&=0xFFFFFFFF
        b&=0xFFFFFFFF
        while b:
            carry=a&b
            a^=b
            b=((carry)<<1)&0xFFFFFFFF
        return a if a<0x80000000 else ~(a^0xFFFFFFFF) 
        
            
            
            
        
        
        
        
        # write code here

发表于 2020-05-27 21:18:10 回复(0)
Python
谢小橙头像 谢小橙
利用位运算代替加法。步骤如下：
【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)
Python
黄沙遮天头像 黄沙遮天 
# -*- coding:utf-8 -*-
class Solution:
    def yihuo(self,num1,num2):
        #第一步首先是各位的一个异或，实现各位相加但是不进位，将其转化为二进制形式
        #其中0和0，还有1和1都是0；1和0，以及0和1都是1.所以我们采用异或的方法
        return num1 ^ num2
    def yu(self,num1,num2):
        #第二步分为一个位与运算，然后向左移动一位；因为第二步中不管是0和0，1和0，0和1都不会
        #产生进位，只有1和1才产生进位，所以采用的是与运算，然后向左移动一位
        return (num1 & num2)<<1
    def Add(self, num1, num2):
        if num1==None&nbs***bsp;num2==None:
            return -1
        while(num2):
            #以num2作为循环条件
            #此时result也可以当作第一步和第二步的和，是一个异或
            result=self.yihuo(num1,num2)
            #计算进位
            num2=self.yu(num1,num2)
            #求负数的补码
            num1=result & 0xffffffff
        #return里需要小心-1的情况，因为-1=1111 1111 1111 1111 1111 1111 1111 1111（二进制）
        return num1 if num1>>31==0 else num1-4294967296

发表于 2020-01-09 19:45:14 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
# 解题思路：位运算实现加法，两个数按异或得到低位，两个数按位与左移一位得到进位，重复前两步直到进位为0
class Solution:
    def Add(self, num1, num2):
        if not num1:
            return num2
        if not num2:
            return num1
        while num2 != 0:
            n1 = num1 ^ num2
            n2 = (num1 & num2) << 1
            num1 = n1 & 0xFFFFFFFF
            num2 = n2
        return num1 if num1 >> 31 == 0 else num1 - 4294967296

发表于 2019-12-10 12:14:14 回复(0)
Python
秋水中的鱼头像 秋水中的鱼
python中的位运算挺烦的,要考虑越界问题,先用sum完成 
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        return sum([num1,num2])


发表于 2019-11-13 12:58:19 回复(0)
Python
化学反应头像 化学反应
python直接递归会超过递归深度限制，改成循环会超时。。。
以下是借鉴大神的溢出检查的方法： 
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # num1 ^ num2: 无进位加法结果
        # (num1 & num2) << 1 ： 进位位
        # 当进位为0时加法结束
        # 0xFFFFFFFF是32位的1，python内部不会检查溢出所以要手动检查，这里视为无符号整数检查
        # 若和的二进制形式小于最大正整数限制（有符号数0x7FFFFFFF）则直接返回
        # ~(num1 ^ 0xFFFFFFFF): 取反加一的逆运算（原码变补码），负数的情况
        while num2:
            num1, num2 = (num1 ^ num2) & 0xFFFFFFFF, ((num1 & num2) << 1) & 0xFFFFFFFF
        return num1 if num1 <= 0x7FFFFFFF else ~(num1 ^ 0xFFFFFFFF)


发表于 2019-11-12 10:30:59 回复(0)
Python
小火箭、头像 小火箭、
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        li = []
        li.append(num1)
        li.append(num2)
        res = sum(li)
        return res
发表于 2019-08-31 16:49:15 回复(0)
Python
Mia_Ye头像 Mia_Ye
😳
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        a = [num1, num2]
        return sum(a)


发表于 2019-08-21 02:01:21 回复(0)
Python
小肚腩是可爱的头像 小肚腩是可爱的
请教大家，我写的Add方法提醒运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大，但是Add2却能通过，这是为什么呢 
    def Add(self, num1, num2):
        while num2!=0:
            temp=(num1 & num2)<<1
            num1=num1 ^ num2
            num2=temp

        return num1
    def Add2(self, num1, num2):
        while num2!=0:
            temp=num1 ^ num2
            num2=(num1 & num2)<<1
            num1=temp&0xFFFFFFFF

        return num1 if num1>>31==0 else num1-4294967296


发表于 2019-08-11 09:04:41 回复(0)
Python
一份路过的offer头像 一份路过的offer 
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
5星上将头像 5星上将 
# -*- coding:utf-8 -*- 
class Solution:  
    def Add(self, num1, num2): 
        return sum(num1,num2)
这样会不会太简单了🤐

编辑于 2019-06-06 15:57:45 回复(0)
Python
Max阿宇头像 Max阿宇
sum
发表于 2019-04-18 19:15:45 回复(0)
Python
PCChris头像 PCChris
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        while num2 != 0:
            sum1 = num1 ^ num2
            carry = (num1 & num2) << 1
            num1 = sum1
            num2 = carry
        return sum1 

剑指offer的解答，程序超时了怎么回事？？

发表于 2019-04-03 18:01:00 回复(1)
Python
内推找我offer多多头像 内推找我offer多多 
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        return sum(list([num1,num2]))

发表于 2019-03-10 21:37:35 回复(0)
提交观点

问题信息

基础数学
难度：
36条回答 115080浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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