We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Two Integers

Number: 371

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta, Bloomberg, Microsoft, Apple, Yahoo, Hulu

Problem Description

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

Key Insights

  • Use bitwise XOR (^) to perform addition without carrying.
  • Use bitwise AND (&) followed by a left shift (<<) to calculate the carry.
  • Repeat the process until there is no carry.
  • This method simulates the addition process using binary arithmetic.

Space and Time Complexity

Time Complexity: O(1) – The loop runs a fixed number of times based on the number of bits. Space Complexity: O(1) – Only constant extra space is used.

Solution

The solution uses bit manipulation to add two numbers without using the + or - operators.

  1. Use XOR (^) on a and b to add the bits where there is no carry.
  2. Use AND (&) to find the positions where both a and b have a 1 (i.e., potential carry). Then shift the result left by one to add in the next higher bit.
  3. Set a to the XOR result and b to the shifted carry.
  4. Repeat steps 1-3 until there is no carry (b equals 0).
  5. Return a which holds the final sum. This approach leverages the bitwise operations to effectively simulate binary addition.

Code Solutions

# Python implementation to add two integers without using + or -
def getSum(a, b):
    # Continue till there is no carry
    while b != 0:
        # XOR gets the sum excluding carries
        sum_without_carry = a ^ b
        # AND finds carries, left shift to apply them to the next bit
        carry = (a & b) << 1
        # Update a with sum without carry and b with carry
        a = sum_without_carry
        b = carry
    return a

# Example usage:
result = getSum(1, 2)
print("Sum:", result)  # Output: Sum: 3
← Back to All Questions