A+B问题

题目描述

给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符

思路

二进制的数字用0、1表示，两数相加即对应位0、1相加，其结果无非还是0、1
存在两种情况：进位、不进位
不进位：考虑用异或。异或运算又叫：不进位相加
进位：进位的bit位，即两数与的结果为1的位。进位需要将两数与的结果左移一位。
所以两数求和，演变成异或的结果和与运算移位后的结果继续求和，考虑递归。
递归终止条件自然是与的结果为0，那么最终结果就是异或的值。

代码

class Solution {

    public int aplusb(int a, int b) {
        // write your code here, try to do it without arithmetic operators.
        if(b == 0) {
            return a;
        }else {
            return repeat(a, b);
        }
    }
    
    private int repeat(int a, int b) {
        int _a = a ^ b;
        int _b = (a & b) << 1;
        if(b != 0) {
           return repeat(_a, _b);
        }else {
            return _a;   
        }
    }
};

考差点

• 递归（递归的思想：参数不同，套路相同，终止条件，逐层返回）
• 位运算（两数异或：加法不进位）