[LintCode]A+B問題
7243 ワード
Bit-by-Bit summation:
Treat a + b as two parts: a + b without carry; carry of a + b; recursively plus part 1 and part 2 until no carry exists.
The code can be further shortened by writing it recursively.
1 class Solution {
2 public:
3 /*
4 * @param a: The first integer
5 * @param b: The second integer
6 * @return: The sum of a and b
7 */
8 int aplusb(int a, int b) {
9 // write your code here, try to do it without arithmetic operators.
10 int res = 0, sum = 0, carry = 0;
11 for (int i = 0; i < 32; i++, a >>= 1, b >>= 1){
12 int d1 = a & 1, d2 = b & 1;
13 sum = (d1 ^ d2 ^ carry);
14 carry = max((d1 & d2), max((d1 & carry), (d2 & carry)));
15 res ^= (sum << i);
16 }
17 return res;
18 }
19 };
Treat a + b as two parts:
1 class Solution {
2 public:
3 /*
4 * @param a: The first integer
5 * @param b: The second integer
6 * @return: The sum of a and b
7 */
8 int aplusb(int a, int b) {
9 // write your code here, try to do it without arithmetic operators.
10 while (b) {
11 int carry = a & b; // carry
12 a ^= b; // plus without carry
13 b = carry << 1; // recursively plus the two parts
14 }
15 return a;
16 }
17 };
The code can be further shortened by writing it recursively.
1 class Solution {
2 public:
3 /*
4 * @param a: The first integer
5 * @param b: The second integer
6 * @return: The sum of a and b
7 */
8 int aplusb(int a, int b) {
9 // write your code here, try to do it without arithmetic operators.
10 if (!b) return a;
11 return aplusb(a ^ b, (a & b) << 1);
12 }
13 };