[Java] Sum two integers without sum operator

Given two integers, return a + b without using sum operator.

Seems like it's time for more bit magic. 

We process our numbers bit by bit starting from LSB, we track a carry, a position in the result sum, and the result sum.

Getting the LSB can be done by:

n & 1

If 1 the bit was set to 1

Then we can calculate the result of the sum:

it will be a 1 only if there is an odd number of ones between lsbA, lsbB and carry:

• 1 + 1 = 0, unless carry was 1
• 1 + 0 = 0, unless carry was 1
• 0 + 0 = 0, unless carry was 1

res = lsbA ^ lsbB ^ carry

Then we can push that bit in the correct place in the final result:

res = res << position

And set it in the final sum:

sum |= res

Also we need to increase position for the next iteration, but we can't use sum operator:

position = -(~position)

We can then calculate the carry for the next iteration:

it will be a 1 if there were at least two ones between lsbA, lsbB, carry:

• 0 + 1 + 0 = 1 no carry
• 1 + 1 + 0 = 0 with carry
• 0 + 0 + 1 = 1 no carry
  
• 1 + 1 + 1 = 1 with carry 

carry = (lsbA & lsbB) | (lsbA & carry) | (lsbB & carry)

we then drop the lsb from both a and b WITHOUT preserving sign (we need it come to us for processing, we can't leave it set in MSB):

a = a >>> 1

b = b >>> 1

and repeat this process until both a and b are 0

One last thing to do after all of this, if there was still a carry left AND we are not trying to set it in position 32 (MSB), set it in the final sum.

You can check my implementation of sum on my Gist along with some tests in SumJTests.