Sum of Two Integers

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

Example 1: Input: a = 1, b = 2 Output: 3

Example 2: Input: a = 2, b = 3 Output: 5

Can you provide an efficient algorithm to achieve this, and explain its time and space complexity? Also, consider edge cases such as negative numbers and potential overflow situations. How would your solution handle these?

# Naive Solution:
# Use the built-in sum() function, which internally uses + operator, but for demonstration.
def getSum_naive(a: int, b: int) -> int:
    """Naive solution using the built-in sum function."""
    return sum([a, b])


# Optimal Solution: Bit Manipulation
def getSum(a: int, b: int) -> int:
    """Calculates the sum of two integers without using + or - operators.

    The approach simulates binary addition using bitwise operators.
    - & (AND) is used to find the carry.
    - ^ (XOR) is used to find the sum (without carry).
    The carry is then left-shifted by one position (carry << 1) to add it in the next iteration.

    Args:
        a (int): The first integer.
        b (int): The second integer.

    Returns:
        int: The sum of the two integers.
    """
    mask = 0xFFFFFFFF  # Mask for 32-bit
    while b != 0:
        carry = (a & b) << 1
        a = (a ^ b) & mask  # Ensure it stays within 32 bits
        b = carry & mask  # Ensure it stays within 32 bits

    # If a is negative, convert it to the correct negative number within 32-bit range
    if (a >> 31) & 1:
        return ~(a ^ mask)
    else:
        return a


# Example Usage:
if __name__ == "__main__":
    print(f"Sum of 1 and 2 (naive): {getSum_naive(1, 2)}")
    print(f"Sum of 1 and 2 (optimal): {getSum(1, 2)}")  # Output: 3
    print(f"Sum of -2 and 3 (optimal): {getSum(-2, 3)}") # Output: 1
    print(f"Sum of -1 and 1 (optimal): {getSum(-1, 1)}") # Output: 0


# Big O Time Complexity Analysis:
# The while loop iterates based on the number of set bits in 'b'.
# In the worst case, it can iterate up to 32 times (for 32-bit integers).
# Therefore, the time complexity is O(1), as it is constant regardless of the input values.


# Big O Space Complexity Analysis:
# The algorithm uses a fixed number of variables (a, b, carry, mask).
# The space used does not depend on the input values.
# Therefore, the space complexity is O(1), constant space.


# Edge Case Handling:
# 1. Negative Numbers: The code correctly handles negative numbers by using a 32-bit mask
#    and checking the sign bit (bit 31). It ensures that the result is properly represented
#    as a 32-bit integer, handling two's complement representation.
#
# 2. Overflow: The 32-bit mask prevents integer overflow by keeping the numbers within the
#    32-bit range. If the result exceeds this range, it will be wrapped around, simulating
#    the behavior of 32-bit integer arithmetic.
#
# 3. Zero: The algorithm handles zero correctly. If either 'a' or 'b' is zero (or both), the
#    loop will terminate appropriately, and the correct sum will be returned.
#
# 4. Large Numbers: Although the numbers are kept within a 32-bit range, large positive and
#    negative numbers are correctly added due to the bitwise operations simulating binary addition.
#    For example, adding the maximum and minimum 32-bit integers will yield the correct wrapped-around result.