Sum of Two Integers Without + Operator

🎯

Sum of Two Integers Without + Operator

mediumBIT_MANIPULATIONFacebookAmazonGoogle

Imagine a low-level embedded system where addition hardware is unavailable or costly, and you need to add two integers using only bitwise operations.

💡 This problem challenges beginners because it forbids the usual '+' operator, forcing them to understand how addition works at the bit level using XOR and AND operations. It helps build intuition about binary arithmetic and bit manipulation.

📋

Problem Statement

Given two integers a and b, return the sum of the two integers without using the '+' or '-' operators.

-2^31 <= a, b <= 2^31 - 1

💡

Example

Input"a = 1, b = 2"

Output3

1 + 2 = 3, computed using bitwise operations without '+'

Input"a = -2, b = 3"

Output1

-2 + 3 = 1, handled correctly with bitwise operations and two's complement

• a = 0, b = 0 → 0
• a = 0, b = 5 → 5
• a = -1, b = 1 → 0
• a = 2^31 - 1, b = 1 → -2^31 (overflow behavior in 32-bit signed int)

⚠️

Common Mistakes

Ignoring integer overflow and sign bits

Incorrect results for negative numbers or large positive numbers

✅ Use masking to simulate 32-bit integer overflow and convert unsigned to signed at the end

Forgetting to shift carry bits left by 1

Infinite loop or incorrect sum because carry bits are not added in correct position

✅ Always shift carry bits left by 1 before next addition iteration

Using recursion without base case or with incorrect base case

Stack overflow or infinite recursion

✅ Base case must be when carry (b) is zero, return a

Not masking intermediate results in Python

Incorrect results due to Python's unlimited integer size and sign extension

✅ Mask intermediate results with 0xFFFFFFFF to simulate 32-bit integer behavior

🧠

Brute Force (Using Python's Built-in Arithmetic)

💡 This approach uses the '+' operator directly to show the simplest way to add two numbers, serving as a baseline to understand why we need alternative methods.

Intuition

Simply add the two numbers using the '+' operator as a black box to verify correctness.

Algorithm

1. Take input integers a and b.
2. Return the sum using the '+' operator.

💡 This approach is trivial but sets the stage for understanding the problem constraints.

</>

Code

def getSum(a: int, b: int) -> int:
    return a + b

# Driver code
if __name__ == "__main__":
    print(getSum(1, 2))  # Output: 3

Line Notes

def getSum(a: int, b: int) -> int:Defines the function signature with type hints for clarity

return a + bUses Python's built-in addition operator to return the sum directly

if __name__ == "__main__":Ensures the test code runs only when the script is executed directly

print(getSum(1, 2))Tests the function with sample input to verify correctness

public class Solution {
    public int getSum(int a, int b) {
        return a + b;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getSum(1, 2)); // Output: 3
    }
}

Line Notes

public int getSum(int a, int b) {Defines the method to add two integers

return a + b;Uses Java's built-in addition operator for simplicity

public static void main(String[] args) {Main method to run the test case

System.out.println(sol.getSum(1, 2));Prints the result of adding 1 and 2

#include <iostream>
using namespace std;

class Solution {
public:
    int getSum(int a, int b) {
        return a + b;
    }
};

int main() {
    Solution sol;
    cout << sol.getSum(1, 2) << endl; // Output: 3
    return 0;
}

Line Notes

int getSum(int a, int b) {Defines the method to add two integers

return a + b;Uses C++ built-in addition operator

int main() {Main function to run the test

cout << sol.getSum(1, 2) << endl;Outputs the sum of 1 and 2

function getSum(a, b) {
    return a + b;
}

// Test
console.log(getSum(1, 2)); // Output: 3

Line Notes

function getSum(a, b) {Defines a function to add two numbers

return a + b;Uses JavaScript's built-in addition operator

console.log(getSum(1, 2));Prints the result for verification

// TestMarks the test code section

⏱

Complexity

TimeO(1)

SpaceO(1)

The addition operator runs in constant time and space as it is a single CPU instruction.

💡 For any input size, this approach instantly returns the sum, so it's the fastest possible but disallowed by problem constraints.

Interview Verdict: Accepted but disallowed by problem constraints

This approach is trivial and not allowed, but it helps clarify the problem and sets a baseline for correctness.

🧠

Iterative Bitwise Sum Using XOR and AND

💡 This approach uses bitwise XOR to add bits without carry and AND to find carry bits, iterating until no carry remains. It teaches how addition works at the bit level.

Intuition

XOR adds bits ignoring carry, AND finds carry bits which are shifted left and added in the next iteration until carry is zero.

Algorithm

1. Initialize sum as XOR of a and b (sum bits without carry).
2. Initialize carry as AND of a and b, shifted left by 1 (carry bits).
3. While carry is not zero:
4. Update a to sum, b to carry, then recompute sum and carry.
5. Return sum when carry is zero.

💡 The loop simulates the addition process bit by bit, handling carry propagation explicitly.

</>

Code

def getSum(a: int, b: int) -> int:
    MASK = 0xFFFFFFFF
    while b != 0:
        carry = (a & b) << 1 & MASK
        a = (a ^ b) & MASK
        b = carry
    # Handle negative numbers
    return a if a <= 0x7FFFFFFF else ~(a ^ MASK)

# Driver code
if __name__ == "__main__":
    print(getSum(1, 2))  # Output: 3
    print(getSum(-2, 3)) # Output: 1

Line Notes

MASK = 0xFFFFFFFFMasks to 32 bits to simulate 32-bit integer overflow behavior

while b != 0:Loop continues until no carry remains

carry = (a & b) << 1 & MASKCalculate carry bits and shift left, mask to 32 bits

a = (a ^ b) & MASKCalculate sum bits without carry, mask to 32 bits

b = carryUpdate b to carry for next iteration

return a if a <= 0x7FFFFFFF else ~(a ^ MASK)Convert from 32-bit unsigned to signed integer

public class Solution {
    public int getSum(int a, int b) {
        int MASK = 0xFFFFFFFF;
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        // Convert to 32-bit signed integer
        if ((a & 0x80000000) != 0) {
            a = ~((~a) & MASK);
        }
        return a;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getSum(1, 2)); // Output: 3
        System.out.println(sol.getSum(-2, 3)); // Output: 1
        System.out.println(sol.getSum(2147483647, 1)); // Output: -2147483648
    }
}

Line Notes

int MASK = 0xFFFFFFFF;Mask to simulate 32-bit integer overflow

while (b != 0) {Loop until no carry bits remain

int carry = (a & b) << 1;Calculate carry bits shifted left

a = a ^ b;Sum bits without carry using XOR

b = carry;Update b to carry for next iteration

if ((a & 0x80000000) != 0) {Check if sign bit is set (negative number)

a = ~((~a) & MASK);Convert from unsigned to signed 32-bit integer

#include <iostream>
using namespace std;

class Solution {
public:
    int getSum(int a, int b) {
        const unsigned int MASK = 0xFFFFFFFF;
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        // Convert to signed 32-bit integer
        if ((a & 0x80000000) != 0) {
            a = ~((~a) & MASK);
        }
        return a;
    }
};

int main() {
    Solution sol;
    cout << sol.getSum(1, 2) << endl; // Output: 3
    cout << sol.getSum(-2, 3) << endl; // Output: 1
    cout << sol.getSum(2147483647, 1) << endl; // Output: -2147483648
    return 0;
}

Line Notes

const unsigned int MASK = 0xFFFFFFFF;Mask to simulate 32-bit integer overflow

while (b != 0) {Loop until carry is zero

int carry = (a & b) << 1;Calculate carry bits shifted left

a = a ^ b;Sum bits without carry using XOR

b = carry;Update b to carry for next iteration

if ((a & 0x80000000) != 0) {Check if sign bit is set (negative number)

a = ~((~a) & MASK);Convert from unsigned to signed 32-bit integer

var getSum = function(a, b) {
    const MASK = 0xFFFFFFFF;
    while (b !== 0) {
        let carry = (a & b) << 1;
        a = (a ^ b) & MASK;
        b = carry & MASK;
    }
    // Convert to signed 32-bit integer
    return (a & 0x80000000) ? ~( (a ^ MASK) ) : a;
};

// Test
console.log(getSum(1, 2)); // Output: 3
console.log(getSum(-2, 3)); // Output: 1
console.log(getSum(2147483647, 1)); // Output: -2147483648

Line Notes

const MASK = 0xFFFFFFFF;Mask to simulate 32-bit integer overflow

while (b !== 0) {Loop until no carry bits remain

let carry = (a & b) << 1;Calculate carry bits shifted left

a = (a ^ b) & MASK;Sum bits without carry, masked to 32 bits

b = carry & MASK;Update b to carry for next iteration, masked

return (a & 0x80000000) ? ~( (a ^ MASK) ) : a;Convert from unsigned to signed 32-bit integer

⏱

Complexity

TimeO(1) average, O(log(max(a,b))) worst case

SpaceO(1)

Each iteration processes carry bits; max 32 iterations for 32-bit integers.

💡 For 32-bit integers, the loop runs at most 32 times, which is very efficient.

Interview Verdict: Accepted and optimal for 32-bit integers

This approach is the standard interview solution demonstrating bitwise addition without '+' operator.

🧠

Recursive Bitwise Sum Using XOR and AND

💡 This approach uses recursion instead of iteration to add two integers using bitwise operations, illustrating the same logic in a different style.

Intuition

Sum bits are XOR of a and b, carry bits are AND shifted left; recursively add sum and carry until carry is zero.

Algorithm

1. If b is zero, return a as the sum.
2. Calculate sum as XOR of a and b.
3. Calculate carry as AND of a and b, shifted left by 1.
4. Recursively call the function with sum and carry.

💡 The recursion naturally handles carry propagation until no carry remains.

</>

Code

def getSum(a: int, b: int) -> int:
    MASK = 0xFFFFFFFF
    if b == 0:
        return a if a <= 0x7FFFFFFF else ~(a ^ MASK)
    sum_ = (a ^ b) & MASK
    carry = ((a & b) << 1) & MASK
    return getSum(sum_, carry)

# Driver code
if __name__ == "__main__":
    print(getSum(1, 2))  # Output: 3
    print(getSum(-2, 3)) # Output: 1

Line Notes

MASK = 0xFFFFFFFFMasks to 32 bits to simulate 32-bit integer overflow

if b == 0:Base case: no carry means addition is complete

return a if a <= 0x7FFFFFFF else ~(a ^ MASK)Convert unsigned to signed integer

sum_ = (a ^ b) & MASKCalculate sum bits without carry

carry = ((a & b) << 1) & MASKCalculate carry bits shifted left

return getSum(sum_, carry)Recursive call with new sum and carry

public class Solution {
    public int getSum(int a, int b) {
        if (b == 0) {
            if ((a & 0x80000000) != 0) {
                a = ~((~a) & 0xFFFFFFFF);
            }
            return a;
        }
        int sum = (a ^ b);
        int carry = (a & b) << 1;
        return getSum(sum, carry);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getSum(1, 2)); // Output: 3
        System.out.println(sol.getSum(-2, 3)); // Output: 1
        System.out.println(sol.getSum(2147483647, 1)); // Output: -2147483648
    }
}

Line Notes

if (b == 0) {Base case: no carry means addition complete

if ((a & 0x80000000) != 0) {Check if sign bit is set (negative number)

a = ~((~a) & 0xFFFFFFFF);Convert from unsigned to signed 32-bit integer

return a;Return final sum

int sum = (a ^ b);Sum bits without carry using XOR

int carry = (a & b) << 1;Carry bits shifted left

return getSum(sum, carry);Recursive call with updated values

#include <iostream>
using namespace std;

class Solution {
public:
    int getSum(int a, int b) {
        if (b == 0) {
            if ((a & 0x80000000) != 0) {
                a = ~((~a) & 0xFFFFFFFF);
            }
            return a;
        }
        int sum = a ^ b;
        int carry = (a & b) << 1;
        return getSum(sum, carry);
    }
};

int main() {
    Solution sol;
    cout << sol.getSum(1, 2) << endl; // Output: 3
    cout << sol.getSum(-2, 3) << endl; // Output: 1
    cout << sol.getSum(2147483647, 1) << endl; // Output: -2147483648
    return 0;
}

Line Notes

if (b == 0) {Base case for recursion

if ((a & 0x80000000) != 0) {Check if sign bit is set (negative number)

a = ~((~a) & 0xFFFFFFFF);Convert from unsigned to signed 32-bit integer

return a;Return final sum

int sum = a ^ b;Sum bits without carry

int carry = (a & b) << 1;Carry bits shifted left

return getSum(sum, carry);Recursive call to continue addition

var getSum = function(a, b) {
    const MASK = 0xFFFFFFFF;
    if (b === 0) {
        return (a & 0x80000000) ? ~( (a ^ MASK) ) : a;
    }
    let sum = (a ^ b) & MASK;
    let carry = ((a & b) << 1) & MASK;
    return getSum(sum, carry);
};

// Test
console.log(getSum(1, 2)); // Output: 3
console.log(getSum(-2, 3)); // Output: 1
console.log(getSum(2147483647, 1)); // Output: -2147483648

Line Notes

const MASK = 0xFFFFFFFF;Mask to simulate 32-bit integer overflow

if (b === 0) {Base case: no carry means addition done

return (a & 0x80000000) ? ~( (a ^ MASK) ) : a;Convert from unsigned to signed 32-bit integer

let sum = (a ^ b) & MASK;Sum bits without carry

let carry = ((a & b) << 1) & MASK;Carry bits shifted left

return getSum(sum, carry);Recursive call to add carry

⏱

Complexity

TimeO(log(max(a,b)))

SpaceO(log(max(a,b))) due to recursion stack

Each recursive call processes carry bits; max 32 calls for 32-bit integers.

💡 Recursion depth equals number of carry propagations, which is at most 32 for 32-bit integers.

Interview Verdict: Accepted but less preferred due to recursion overhead

This approach is elegant but may cause stack overflow for large inputs; iterative is preferred in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always implement the iterative bitwise approach (Approach 2) as it is optimal and accepted. The brute force is only for explanation, and recursion is elegant but less practical.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Using '+')	O(1)	O(1)	No	N/A	Mention only - disallowed by problem
2. Iterative Bitwise Sum	O(log(max(a,b)))	O(1)	No	N/A	Code this approach
3. Recursive Bitwise Sum	O(log(max(a,b)))	O(log(max(a,b))) due to recursion stack	Yes (deep recursion)	N/A	Mention as alternative, avoid coding

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying constraints, then explain brute force, and finally implement the optimal bitwise approach.

How to Present

Clarify the problem constraints and confirm no '+' or '-' operators allowed.State the brute force approach using '+' operator to establish baseline correctness.Explain the bitwise approach using XOR and AND to simulate addition.Implement the iterative bitwise solution with masking for 32-bit integers.Test with positive, negative, zero, and overflow edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of bitwise operations, handling of negative numbers, and ability to simulate addition without '+' operator.

Common Follow-ups

• How would you handle overflow in languages without fixed integer sizes? → Use masking or BigInteger libraries.
• Can you implement subtraction without '-' operator? → Use similar bitwise logic with two's complement.

💡 Follow-ups test your ability to extend bitwise logic to related operations and handle language-specific integer behaviors.

🔍

Pattern Recognition

When to Use

1) Asked to add integers without '+' or '-' operators; 2) Problem hints at bitwise operations; 3) Need to simulate addition at bit level; 4) Handling carry bits explicitly.

Signature Phrases

without using + operatorbitwise operationssimulate additioncarry bits

NOT This Pattern When

Problems that require arithmetic but allow '+' operator or focus on arithmetic sequences rather than bitwise manipulation.

Similar Problems

Add Two Numbers - similar bitwise addition logicMultiply Two Integers Without * Operator - extends bitwise manipulationSubtract Two Integers Without - Operator - uses two's complement and bitwise

Practice

1. You need to determine if a given positive integer can be expressed as 4 raised to some integer power (i.e., n = 4^k for k ≥ 0). Which approach guarantees an optimal O(1) time solution without loops or recursion?

easy

A. Use logarithms to check if log base 4 of the number is an integer.

B. Iteratively divide the number by 4 until it becomes 1 or a non-divisible remainder is found.

C. Check if the number is a power of two and then verify if the set bit is in an even position using bitmasking.

D. Use dynamic programming to build up powers of four and compare with the number.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for a constant-time check to determine if a number is a power of four, which means no loops or recursion.

2. Step 2: Evaluate approaches for O(1) time

   Using bitmasking to check if the number is a power of two and if the single set bit is in an even position is a known O(1) approach. Logarithm checks involve floating point operations and can have precision issues, so they are not guaranteed to be optimal or reliable in constant time. Iterative division and dynamic programming are not O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmasking approach uses constant time bit operations [OK]

Hint: Bitmasking checks power of two and bit position in O(1)

Common Mistakes:

• Confusing power of two check with power of four
• Using loops despite O(1) requirement
• Relying on floating point logarithm checks which can be imprecise

2. Given the following code and input, what is the final returned list?

easy

A. [2, 5]

B. [5, 4]

C. [4, 5]

D. [2, 4]

Solution

1. Step 1: Compute xor of all elements

   xor = 2 ^ 4 ^ 2 ^ 5 = (2 ^ 2) ^ 4 ^ 5 = 0 ^ 4 ^ 5 = 1 (binary 0001)

2. Step 2: Find rightmost set bit and partition

   set_bit = xor & (-xor) = 1 & (-1) = 1. Partition nums by bit 1: group1 (bit set): 5, group2 (bit not set): 2,4,2. XOR group1 = 5, XOR group2 = 4.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches unique elements [OK]

Hint: Rightmost set bit partitions unique numbers correctly [OK]

Common Mistakes:

• Mixing order of output
• Incorrect xor calculation
• Miscomputing set bit

3. You need to generate all possible subsets of a given set of unique integers. Which approach guarantees an optimal solution that systematically enumerates all subsets without missing or duplicating any, and can be implemented efficiently using bitwise operations?

easy

A. Greedy algorithm that picks elements based on local optimality

B. Bitmask enumeration that uses binary representation to generate all subsets

C. Dynamic programming approach similar to knapsack problem

D. Sorting the array and using two pointers to find subsets

Solution

1. Step 1: Understand the problem requires generating all subsets

   Generating all subsets means enumerating 2^n combinations, where n is the number of elements.

2. Step 2: Identify approach that systematically covers all subsets

   Bitmask enumeration uses binary numbers from 0 to 2^n - 1, where each bit represents inclusion/exclusion of an element, ensuring all subsets are generated exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets without duplicates [OK]

Hint: Bitmask maps bits to element inclusion [OK]

Common Mistakes:

• Confusing greedy or DP as suitable for subset enumeration

4. Identify the bug in the following code that attempts to count the number of 1 bits in a signed 32-bit integer:

def hammingWeight(n: int) -> int:
    count = 0
    while n != 0:
        count += n & 1
        n >>= 1
    return count

medium

A. The loop condition 'while n != 0' causes infinite loop for negative numbers due to sign extension.

B. The bitwise AND operation 'n & 1' is incorrect; it should be logical AND 'n && 1'.

C. The right shift operator 'n >>= 1' should be replaced with left shift to count bits correctly.

D. The initial count variable should be initialized to 1 instead of 0.

Solution

1. Step 1: Understand signed right shift behavior

   In Python, right shifting a negative number propagates the sign bit, so n never becomes zero.

2. Step 2: Analyze loop condition

   Because n != 0 remains true for negative numbers, the loop never terminates, causing infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Signed right shift on negative numbers causes infinite loop [OK]

Hint: Signed right shift on negatives causes infinite loop [OK]

Common Mistakes:

• Confusing bitwise AND with logical AND
• Wrong shift direction
• Incorrect count initialization

5. The following code attempts to reverse bits of a 32-bit unsigned integer using divide and conquer masks:

def reverseBits(n: int) -> int:
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
    n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
    n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
    n = (n >> 16) | (n << 16)  # Bug here: missing mask
    return n

What is the bug in this code?

medium

A. Line 4: The mask 0x00ff00ff is incorrect for byte swapping.

B. Line 1: Incorrect mask 0x55555555 used for swapping bits.

C. Line 3: Left shift by 4 bits should be right shift.

D. Line 5: Missing mask after shifting left and right by 16 bits, causing overflow beyond 32 bits.

Solution

1. Step 1: Identify the last step

   The last line shifts bits by 16 left and right but does not mask the result to 32 bits.

2. Step 2: Understand impact

   Without masking, bits can overflow beyond 32 bits, causing incorrect reversal results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Masking with 0xffffffff fixes overflow [OK]

Hint: Always mask after large shifts to keep 32-bit result [OK]

Common Mistakes:

• Forgetting to mask after left shifts
• Misusing masks in earlier steps
• Confusing left and right shifts