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

/**
 * 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
 * <p>
 * 示例:
 * 输入: a = 1, b = 1
 * 输出: 2
 * <p>
 * 提示：
 * a, b 均可能是负数或 0
 * 结果不会溢出 32 位整数
 *
 *  0000 0001
 *  0000 0101
 *
 *  进位和   0000 0010
 *  非进位和 0000 0100
 *
 *  观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。因此，无进位和 n 与进位 c 的计算公式如下；
 * {
 *  n=a⊕b非进位和：异或运算
 *  c=a&b<<1进位：与运算+左移一位
 * }
 * （和 s ）==（非进位和 n ）+（进位 c ）。即可将 s=a+b 转化为：
 *  s=a+b⇒s=n+c
 * 循环求 n 和 c ，直至进位 c=0 ；此时 s=n，返回 n 即可。
 *
 *
 */
public class Solution11 {
    public int add(int a, int b) {
        // n: 非进位和   c：进位和
        // 循环是让进位和为0
        while(b!=0){
            int c = (a & b) << 1;
            int n = a^b;
            a=n;
            b=c;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(new Solution11().add(9, 9));
    }
}