Sum of two integers

Posted on Edited on In Word count in article: 217 Reading time ≈ 1 mins.

## Introduction

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example: Given a = 1 and b = 2, return 3.

Solution

As operators are not allow to use for addition, we can use bit manipulation to solve this problem. For example,a = 110110 and b = 011010, then carry = a & b = 010010 and if a digit is 1, then it means that both a and b have 1 at this digit and needs to carry to the next digit. The next step is to calculate xor = a ^ b = 101100 and if a digit is 1, then it means that a and b have different values (one is 0 and the other is 1). After the calculation of two parts, we shift carry to the left by one digit and add it back to the other part, the addition is equal to the sum of two original numbers, so a + b = xor + carry << 1. Repeat the steps until carry is equal to 0 and the other part xor is the sum of two integers.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
  public int getSum(int a, int b) {
    if(a == 0) return b;
    if(b == 0) return a;

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