Data Structures & Algorithms in Java – Binary – Sum of two integers

Problem :

Given two integers, add them without using + and – operators.

Input:

a = 3

b= 5

Output:

8

Try out the solution here:

https://leetcode.com/problems/sum-of-two-integers/

Hint:

• Use bitwise operators

Solution:

Let’s solve the problem using bitwise operators XOR, AND and SHIFT.

Adding two binary numbers is equal to performing XOR operation between them and then adding the carry forward to the resulting sum until there is no carry forward left.

XOR operation gives the sum of two numbers except the carry forward added.

So you have to keep adding the carry forward separately using XOR operation again until there is no carry forward.

The carry forward number can be found by performing AND operation between the two operands and then shifting the number by 1 place to the left.

ALGORITHM:

STEP1: Until there is no carry forward left:

STEP 1a: Calculate carry forward number by performing AND operation between the two operands

STEP 1b: Perform XOR operation between the two operands . This gives the sum without the carry forward added, assign the result to the first operand itself.

STEP 1c: Shift the carry forward calculated in step 1a by one position to the left and assign it to b. This way it becomes the second operand (the first operand now being the sum of the two operands without the carry forward added – XOR)

STEP2: Return the first operand which now has the final result

class Solution {
    public int getSum(int a, int b) {
     
        
        while(b!=0){
            
            int carry = a & b;
            
            a = a ^ b;
            
            b = carry << 1;
        }
        
        return a;
    }
}

You can also reduce the above code using recursion as below:

class Solution {
    public int getSum(int a, int b) {
     
        
        if(b == 0){
            
            return a;
        }
        
        
       return getSum(a^b,(a&b)<<1);
    }
}

Example:

Let’s add the binary numbers 10 (decimal number 2) and 11 (decimal number 3) using bitwise operators.

First XOR 10 and 11:

10 ^ 11 = 01

XOR operation means if both the operands are the same it returns 0 , else 1

Now , lets calculate the carry forward of 10 and 11.

To do this first perform AND between 10 and 11

10 & 11 = 10

AND operation means if both the operands are 1 it will return 1 else 0.

Now let’s calculate the carry forward by left SHIFTing the above value by 1 position

10 << 1 = 100

So the XOR result is 01

carry forward is 100

Now repeat the steps from the beginning with XOR result as one operand and the carry forward as the other operand

Perform XOR:

01 ^ 100 = 101

Perform AND between 01 and 100

01 & 100 = 000

Left shift this by 1 which also gives 0.

So carry forward is 0 now , you need not proceed further.

Return the last XOR result which is 101

101 is equal to 5 and we got the answer!

That’s it!