剑指Offer（四十八）-- 不使用加减乘除实现加法

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

示例1

输入

1,2

返回值

3

思路以及解答

这道题不让使用加减乘除，那么我们只能考虑其他的方向，比如位运算，位运算可以巧妙的实现加和的操作。

首先让我们来了解一下位运算，

而如果两个数相加，肯定是两个数的二进制相加，再来说说补码的概念，计算机存储的时候，存储的是补码。

• 正数的原码=反码=补码
• 负数的补码=反码+1

假设现在想要计算a和b的和，那么a的二进制表示的第i位，假设为a(i),同样b的是b(i)。

二进制的每一位相加，无非两种结果，一种是进位，一种是没有进位。

从上面的结果可以看出，a+b的每一位相加，如果不进位的话，其结果是异或操作的值，那么如果是有进位呢？

可以发现无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）

而每一位的值，都等于无进位的结果+进位结果（移动一位）的结果。我们可以先用nums1&nums求解出每个都是1的位，也就是求解出进位，每次进位向左边移动一位，接着求解num1^num2，也就是两个数不进位相加的结果，赋值给num1，进位的结果赋值给nums2；循环计算，直到进位为0；

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

时间复杂度为O(n)，遍历完所有的进位即可。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -