算法题每日一练—第55天：不用加号的加法

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、问题描述

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

题目链接：不用加号的加法。

二、题目要求

样例

输入: a = 11, b = 13
输出: 24
复制代码

考察

1.位运算基础、面试题
2.建议用时10~30min
复制代码

三、问题分析

本题是位运算的第10题，没了解过位运算相关知识点可以看这一篇文章，讲解比较详细：

算法题每日一练—第45天：位运算。

这一题主要考察的还是计算机的底层，要与位运算联系起来，我一开始怎么也没想到，后来看题解时发现了一个有趣的回答：

class Solution {
public:
    int add(int a, int b) {
        return a-(-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时，输出结果。

四、编码实现

class Solution {
public:
    int add(int a, int b) {
        if(b == 0)//进位没有，输出结果      
            return a;
        else//递归运算
            return add(a^b, ((unsigned int)a&b)<<1);
    }
};
复制代码

unsigned int代表的是无符号位，要加上不然力扣处理负数的时候会报错。

五、测试结果