Sunday, March 1, 2015

Addition without any operators


Write a function that adds two numbers.You should not use + or any arithmetic operators.

Well, if we cannot use any operators, the only approach left is bit manipulation. 

Consider normally how we would add numbers. There are two parts, first addition, then carry. If we add numbers without carry, then 123 + 987 is 000. If only consider carry, then 123 + 987 is 1110. So in the end if we add two results together, we will have 123 + 987 = 1110 + 000 = 1110. 

Now the next thing, how we can do it with bits. The addition part, bit[i] will be 0 if both bits[i] in a and b is 0 or 1, yup, XOR. The carry part, bit[i] will be 1 if both bits[i - 1] in a and b is 1. It's AND, with 1 position left shift. 


public static int addition(int a, int b){
  if (b == 0)
   return a;
  int sum = a ^ b;
  int carry = (a & b) << 1;
  return addition(sum, carry);
 }

No comments:

Post a Comment