65. 不用加减乘除做加法

题目链接

Leetcode

题目描述

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

解题思路

a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。

递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。负数用补码表示，同样适用，进位最多左移 32 次。

例如 5 + 3，即 101 + 011：无进位和为 110，进位为 010；110 + 010 的无进位和为 100，进位为 100；100 + 100 的无进位和为 000，进位为 1000；最后进位为 0，结果为 1000，即 8。

public int encryptionCalculate(int dataA, int dataB) {
    return dataB == 0 ? dataA : encryptionCalculate(dataA ^ dataB, (dataA & dataB) << 1);
}