# A + B Problem

## Problem

Write a function that add two numbers A and B. You should not use + or any arithmetic operators.

Notice: There is no need to read data from standard input stream. Both parameters are given in function aplusb, you job is to calculate the sum and return it.

## Clarification

Are a and b both 32-bit integers? Yes.

Can I use bit operation? Sure you can.

## Example

Given a=1 and b=2 return 3

## Challenge

Of course you can just return a + b to get accepted. But Can you challenge not do it like that?

## Solution

+ is not allowed to use, however we can directly manipulate bits to simulate the plus operation.

In its binary format, 1 + 0 will be 1, 0 + 0 will be 0, 1 + 1 will become 0, and the carry becomes 1. So the result without carry can be calculated by xor a ^ b, and the carry a & b, if carry is not 0, shift it left by 1, and add again:

while(b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}

For example, a = 1(binary as 1), b = 3(binary as 11)

======    Iteration #1    ======
a =          1
b =         11
carry(a & b) =          1
new a(a ^ b) =         10
new b(shifted carry) =         10

======    Iteration #2    ======
a =         10
b =         10
carry(a & b) =         10
new a(a ^ b) =          0
new b(shifted carry) =        100

======    Iteration #3    ======
a =          0
b =        100
carry(a & b) =          0
new a(a ^ b) =        100
new b(shifted carry) =          0

Final Result: 4

Try to plugin other numbers to fully understand how it works: Source Code

Since negative numbers are in the form of Two's Complement, they can be treated in the same way. For example a = 1, b = -3:

======    Iteration #1    ======
a =                                1
b = 11111111111111111111111111111101
carry(a & b) =                                1
new a(a ^ b) = 11111111111111111111111111111100
new b(shifted carry) =                               10

======    Iteration #2    ======
a = 11111111111111111111111111111100
b =                               10
carry(a & b) =                                0
new a(a ^ b) = 11111111111111111111111111111110
new b(shifted carry) =                                0

Final Result: -2

## Code - Java

class Solution {
/*
* param a: The first integer
* param b: The second integer
* return: The sum of a and b
*/
public int aplusb(int a, int b) {
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
};