Question 18

Interview Question Series | Season 2

Problem: Add Two Integers Without Using the `+` Operator

Given two integers, x and y, write a function to add them together without using the + operator. You must use bitwise operations to perform the addition.

The bitwise approach involves using XOR and AND operators to handle the carry and sum, respectively. Here’s how it works:

The XOR operator (^) can be used to add numbers without considering the carry.
The AND operator (&) can be used to find the carry bits.
The carry is then shifted left by 1 to be added in the next iteration.

Example:

For example, if we add 9 and 9:

In binary, 9 is 1001 and the sum would be 18 which is 10010 in binary.

Algorithm Explanation:

Use XOR (^) to add the two numbers and ignore the carry.
Use AND (&) to calculate the carry.
Shift the carry left by 1 bit and repeat the process until there is no carry left.

C Code:

#include <stdio.h>
#include <stdlib.h>

int add(int x, int y)
{
    int z = 0;
    // While there is a carry
    while (y != 0)
    {
        // Calculate carry
        z = x & y;
        // Sum without carry
        x = x ^ y;
        // Shift carry left
        y = z << 1;
    }
    return x;  // Final sum
}

int main()
{
    int num1 = 9, num2 = 9;
    printf("Sum: %dn", add(num1, num2));  // Output: Sum: 18
    return 0;
}

How the Code Works:

XOR Operation (x ^ y):
- This adds the two numbers but doesn’t take the carry into account.
AND Operation (x & y):
- This finds the common bits where a carry is generated (i.e., both bits are 1).
Shift Left (<< 1):
- This shifts the carry to the left by one position to be added in the next iteration.
The process continues until the carry (y) is zero, meaning the addition is complete.

Example Walkthrough:

For x = 9 and y = 9 (binary 1001 and 1001 respectively):