Add two numbers without using arithmetic operators

Given two integers a and b, the task is to find the sum of a and b without using + or - operators.

Examples: 

Input: a = 10, b = 30
Output: 40

Input: a = -1, b = 2
Output: 1

Approach:

The approach is to add two numbers using bitwise operations. Let's first go through some observations:

• a & b will have only those bits set which are set in both a and b.
• a ^ b will have only those bits set which are set in either a or b but not in both.

If we want to calculate the sum of a and b such that a and b has no common set bit, then a ^ b is same as a + b. So, we can say that a + b without carry = a ^ b.

How to handle the case when we have carry, that is a and b has common set bits?

To calculate the carry, we know that carry will only have the common set bits of a and b, shifted 1 place to the left. So, we can say that carry = (a & b) << 1.

Now, the problem is reduced to calculating the sum of (a + b without carry) and carry. This is again the same problem: sum of two numbers where the first number = (a + b without carry) and second number = carry. So, we can repeatedly calculate carry and sum without carry, till carry is not reduced to 0.

Working:

Note: The above approach will work perfectly for languages like C++, Java, C# and JavaScript in which an integer has a size of 32 bits but in Python, we need to handle the overflow separately by creating a 32-bit mask of 1's.

Below is the implementation of the above algorithm:

// C++ Program to add two numbers without using arithmetic operators  #include <bits/stdc++.h> using namespace std; // function to add two numbers without using arithmetic operators int sum(int a, int b) {    // Iterate till there is no carry   while (b != 0) {     // carry contains common set bits of a and b, left shifted by 1  int carry = (a & b) << 1;  // Update a with (a + b without carry)  a = a ^ b;    // Update b with carry  b = carry;   }   return a; }  int main() {  int a = -1, b = 2;    cout << sum(a, b);  return 0;  }  

// C Program to add two numbers without using arithmetic operators  #include <stdio.h> // function to add two numbers without using arithmetic operators int sum(int a, int b) {    // 32 bit mask in hexadecimal  long mask = 0xffffffff;  // Iterate till there is no carry   while ((b & mask) != 0) {     // carry contains common set bits of a and b, left shifted by 1  int carry = ((a & b) & mask) << 1;  // Update a with (a + b without carry)  a = a ^ b;    // Update b with carry  b = carry;   }   return a & mask; }  int main() {  int a = -1, b = 2;    printf("%d\n", sum(a, b));  return 0;  } 

// Java Program to add two numbers without using arithmetic operators  class GfG {  // function to add two numbers without using arithmetic operators  static int sum(int a, int b) {    // Iterate till there is no carry   while (b != 0) {     // carry contains common set bits of a and b, left shifted by 1  int carry = (a & b) << 1;  // Update a with (a + b without carry)  a = a ^ b;    // Update b with carry  b = carry;   }   return a;  }   public static void main(String[] args) {  int a = -1, b = 2;    System.out.println(sum(a, b));  }  } 

# Python Program to add two numbers without using arithmetic operators  # function to add two numbers without using arithmetic operators def sum(a, b): # 32 bit mask in hexadecimal mask = 0xffffffff # Iterate till there is no carry  while (b & mask) != 0: # carry contains common set bits of a and b, left shifted by 1 carry = (a & b) << 1 # Update a with (a + b without carry) a = a ^ b # Update b with carry b = carry return a & mask if b > 0 else a a = -1 b = 2 print(sum(a, b)) 

// C# Program to add two numbers without using arithmetic operators  using System; class GfG {    // function to add two numbers without using arithmetic operators  static int Sum(int a, int b) {    // Iterate till there is no carry   while (b != 0) {    // carry contains common set bits of a and b, left shifted by 1  int carry = (a & b) << 1;  // Update a with (a + b without carry)  a = a ^ b;  // Update b with carry  b = carry;  }  return a;  }  static void Main() {  int a = -1, b = 2;  Console.WriteLine(Sum(a, b));  } } 

// JavaScript Program to add two numbers without using arithmetic operators  // function to add two numbers without using arithmetic operators function sum(a, b) {    // Iterate till there is no carry   while (b !== 0) {    // carry contains common set bits of a and b, left shifted by 1  let carry = (a & b) << 1;  // Update a with (a + b without carry)  a = a ^ b;    // Update b with carry  b = carry;   }   return a; } const a = -1, b = 2; console.log(sum(a, b)); 

1

Time Complexity: O(max(number of bits in a, number of bits in b))
Auxiliary Space: O(1)