【算法日记66】不用加减乘除做加法

题目描述

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

不能使用四则运算，就只能使用位运算。在二进制中，两数相加相当于两个数的二进制进行异或运算。考虑到进位问题，异或运算得到的结果其实是本位，例如1^1 = 0，其进位1被忽略了。需要再算一次进位，二进制中只有两个1相加时才可能有进位1，因此进位的结果相当于两个数做与运算然后左移一位。

例如计算 1 + 1 = 2。相当于先计算本位 1 ^ 1 = 0，然后计算进位 1 & 1 = 1，1 « 1 = 10，然后进位和本位相加 0 ^ 10 = 10，结果即为2。

public class Solution {
    public int Add(int num1,int num2) {
        while (num2 != 0) {  // 循环到没有进位为止
            int sum = num1 ^ num2;  // 本位
            num2 = (num1 & num2) << 1;  // 进位
            num1 = sum;
        }
        return num1;
    }
}