Algorithm

LintCode /A + B Problem

Problem Summary

Write a function that add two numbers A and B without using “+” or any arithmetic operators.

Solution

Let x = a ^ b, y = (a&b) << 1. Then x contains the different digits of a and b. (a&b) contains the same digits of a and b; y denotes the carrying digits. So when we add x and y, we get the sum of a and b.

So we use a while loop to implement the process. Each time we use x and y to replace a and b, respectively. When the carry is zero, we have got the answer.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    /*
     * @param : An integer
     * @param : An integer
     * @return: The sum of a and b
     */
    int aplusb(int a, int b) {
    	int x,y;
    	while (b)
    	{
    		x = a^b;
    		y = (a&b) << 1;
    		a = x;
    		b = y;
    	}
    	return a;
    }
};