jz65.不用加减乘除做加法

题目描述

题解

因为不能使用加减乘除, 那么只能考虑位运算, 对于二进制下的两个数某位的加法有以下规律

a(i)	b(i)	无进位和n(i)	进位c(i+1)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。因此，无进位和 n与进位 c的计算公式如下；

循环求 n 和 c，直至进位 c = 0 ；此时 s = n，返回 n即可。

public int add(int a, int b) {
    while (b != 0) {
        int c = (a & b) << 1;
        a ^=b;
        b = c;
    }
    return a;
}