一、问题描述
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
题目链接:不用加号的加法
二、题目要求
样例
输入: a = 11, b = 13 输出: 24
考察
位运算基础、面试题 建议用时10~30min
三、问题分析
本题是位运算的第10题,没了解过位运算相关知识点可以看这一篇文章,讲解比较详细:
这一题主要考察的还是计算机的底层,要与位运算联系起来,我一开始怎么也没想到,后来看题解时发现了一个有趣的回答:
classSolution { public: intadd(inta, intb) { returna-(-b); } };
我大为震惊,确实没用到加法!
闲话少说,开始解题吧!这一题要用到位运算里面的异或、与、移位计算,这部分知识上面的文章链接里面都有,我就简单的讲一下。
以样例为例:
11->二进制:1011 13->二进制:1101 异或: 0110 与:1001 对与的结果左移:10010
异或加法操作只能计算一个位置是0,另一个位置是1的操作,假如两个位置都是1,那么本应该进位的结果,异或之后就变成0了,这个缺陷需要用与弥补。
与在这一题针对进位,比如101^101=101,只需要左移一位进位就完成了1010,进位完成
当不存在进位时,那么异或大法就成了。
我详细写一下步骤,a=a^b代表运算 , b=(a&b)<<1代表进位:
a 0110 10100 10000 11000 b 10010 100 1000 0000
当b等于0时,输出结果。
四、编码实现
classSolution { public: intadd(inta, intb) { if(b==0)//进位没有,输出结果 returna; else//递归运算returnadd(a^b, ((unsignedint)a&b)<<1); } };
unsigned int代表的是无符号位,要加上不然力扣处理负数的时候会报错。