[数据结构与算法]0位运算/数学简单 剑指 Offer 65. 不用加减乘除做加法

剑指 Offer 65. 不用加减乘除做加法

描述

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

分析

a ^ b 等同于 a + b且不做进位（无进位和）。
(a & b) << 1等同于 a + b的进位（进位 ）。
因此 a+b等于（a ^ b）+（（a & b) << 1） ，但这个相加仍然存在进位，所以需要一直递归此过程，直到进位(a & b) << 1为0，此时的a ^ b便是 a+b的最终结果。

为什么进位一定会变为0？ 我的理解是进位一直在不断的向左移动，因为相加数值的二进制的1的个数是有限的，相加不可能一直存在进位，所以进位一定会最终变为0，即不在存在进位，这时候的无进位和就是和。

class Solution {
    public int add(int a, int b) {
        int i = a ^ b;
        int j = (a & b) << 1;
        if(j == 0){
            return i;
        }
        return add(i,j);
    }
}