Bitwise Operators: Given 2 integers, perform bitwise recursive addition of integers

Problem Statement:

You are given 2 integers, you need to perform bitwise recursive addition of 2 integers.

Example:

x = 10
y = 15

Output: 25

Solution Explanation:

We know that,

XOR (x ^ y) gives the sum without array

AND (x & y) identifies the carry, then shifted to left.

Then recursion continues until the carry becomes 0.

In the solution, the function calculate the carry and adds it to the sum using XOR operator.

Then the function will then recursively calls itself, with new sum(from XOR) and new carry (from AND shift left).

This will be continued till there is no carry left, till the sum is fully computed.

Time Complexity: O(n)

Space Complexity: O(n)

Code Solution

#include<iostream>
using namespace std;

int addRecursively(int x, int y) 
{

    // if there is no carry, return sum
    if (y == 0) 
    {
        return x;
    }

    // calcualte carry, and update x and y value
    int carry = (x & y) << 1;
    return addRecursively((x ^ y), carry);
}

int main() 
{
  
    int x = 10, y = 15;

    cout << addRecursively(x, y);
    return 0; 
}

Output

25