Leetcode 371. Sum of Two Integers

Problem

We are given two integers, a and b. We need to return sum of a and b but there is a restriction i.e we are NOT allowed to use "+" and "-" operators. We need to find some alternate method to calculate the sum.

Let's take an example. Suppose a = 1 and b = 2, then the output should be 3.

Approach

The problem can be solved using bitwise operators. The idea is to use XOR ^ operation to handle simple addition (without carry), and use AND & and SHIFT LEFT << operation to handle carry.

Bitwise XOR operation can handle the part where no carry is involved. For instance, in binary representation, 2 is 10 and 1 is 01

1
2
32 : 1 0
41 : 0 1
5------
6^ : 1 1  (which is equal to `3` in decimal)

When we perform XOR operation on any two bits, it results in the sum of them. That's why 2 ^ 1 = 3

Bitwise AND operation is used to handle carry, if any. But this is not enough. AND operation gives us carry, we have to shift this carry 1 bit to the left to add it in the next iteration. This is because this carry will be added to next bit on left.

1
2c++
3carry = a & b;
4carry <<= 1;

The algorithm continue this process recursively until there is no carry i.e b == 0.

Solution

Below are the solution in multiple languages,

Python

1
2python
3class Solution:
4  def getSum(self, a: int, b: int) -> int:
5    MASK = 0x100000000
6    MAX_INT = 0x7FFFFFFF
7    MIN_INT = MASK - MAX_INT
8
9    a %= MASK
10    b %= MASK
11
12    while b != 0:
13      carry = (a & b) << 1
14      a ^= b
15      b = carry % MASK
16
17    return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)

Java

1
2java
3class Solution {
4 public int getSum(int a, int b) {
5    if(b == 0){ //No carry so we can return a
6      return a;
7    }
8    //Sum without taking into account the carry
9    int sum = a ^ b; 
10    //Take carry into account usgin AND and left shifting by one
11    //as the carry should be added to the next bit
12    int carry = (a & b) << 1; 
13    return getSum(sum, carry);
14  }
15}

JavaScript

1
2javascript
3var getSum = function(a, b) {
4    while (b !== 0) {
5        let carry = a & b;
6        a = a ^ b;
7        b = carry << 1;
8    }
9
10    return a;
11};

C++

1
2cpp
3class Solution {
4 public:
5  int getSum(unsigned a, unsigned b) {
6    while (b) {                      // Still have carry bits
7      const unsigned carry = a & b;  // Record carry bits
8      a ^= b;                        // XOR works like + w/o handling carry bits
9      b = carry << 1;
10    }
11
12    return a;
13  }
14};

C#

1
2csharp
3public class Solution {
4    public int GetSum(int a, int b) {
5        while(b != 0){
6            int carry = a & b;
7            a = a ^ b;
8            b = carry << 1;
9        }
10        return a;
11    }
12}

Ruby

Like previous code implementations, the Ruby version accomplishes the same goal using bitwise operators. The AND operator is used to find the carry bits and the XOR operator is used to calculate the sum.

1
2ruby
3def get_sum(a, b)
4    while(b != 0)
5        carry = a & b
6        a = a ^ b
7        b = carry << 1
8    end
9    a
10end

Kotlin

In Kotlin, we first check if the second number b is 0. In this case, we can simply return a as there are no carry bits. After calculating the sum without considering carry bits and the carry using AND and bit shift operators, we call the same function recursively.

1
2kotlin
3fun getSum(a:Int, b:Int):Int {
4    return if(b==0)
5        a
6    else
7        getSum(a xor b, (a and b) shl 1)
8}

Go

In Go, the approach is similar. We calculate the sum and carry separately using XOR and AND operators, and shift the carry by 1 to left to consider it for the next iteration.

1
2go
3func getSum(a int, b int) int {
4    for b != 0 {
5        carry := a & b
6        a = a ^ b
7        b = carry << 1
8    }
9    return a
10}

Swift

In Swift, we loop until b is not equal to 0. The AND operator calculates the carry bits, the XOR operator calculates the sum without carry bits and the left shift moves the carry bits to the next higher bit for next iteration.

1
2swift
3func getSum(_ a: Int, _ b: Int) -> Int {
4    var a = a
5    var b = b
6    while b != 0 {
7        let carry = a & b
8        a = a ^ b
9        b = carry << 1
10    }
11    return a
12}

These are the solutions in multiple programming languages to solve this problem using bitwise operators. The iterative approach ensures that our solution has a time complexity of O(1) and space complexity also as O(1), making it extremely efficient.