## Solution 1: Bitwise XOR and carry - O(1) time / O(1) space The key insight: addition in hardware does exactly two things. XOR computes the sum bits without carries (1+0=1, 0+1=1, 0+0=0, 1+1=0 with carry). AND followed by a left shift computes where the carry bits go. Repeat until there are no more carries. Here is why it works: - `a ^ b` gives the sum of each bit position ignoring carry. - `(a & b) << 1` gives the carry that needs to be added to the next higher bit. - Repeat: the new `a` is the XOR result, the new `b` is the carry. Keep going until the carry is zero. For two positive integers, this terminates quickly. The carry shifts left each iteration, so after at most 32 iterations (the number of bits) the carry becomes zero. **Python complication:** Python integers have arbitrary precision - there is no fixed 32-bit boundary. This means a negative `b` in 2s complement representation will never become 0 in the carry loop, because Python extends the sign bit infinitely. The fix: mask to 32 bits with `& 0xFFFFFFFF` at each step, then interpret the result as a signed 32-bit integer at the end. ```python class Solution: def getSum(self, a: int, b: int) -> int: MASK = 0xFFFFFFFF # 32 bits of ones MAX = 0x7FFFFFFF # largest positive 32-bit signed int while b & MASK: carry = (a & b) << 1 a = a ^ b b = carry a &= MASK b &= MASK # If a fits in a signed 32-bit int, return it directly. # Otherwise, convert the two's complement bit pattern to a negative Python int. if a <= MAX: return a return ~(a ^ MASK) ``` Step through `a=2 (010), b=3 (011)`: - Iteration 1: carry = (010 & 011) << 1 = 010 << 1 = 100. a = 010 ^ 011 = 001. b = 100. - Iteration 2: carry = (001 & 100) << 1 = 0. a = 001 ^ 100 = 101 = 5. b = 0. Done. Step through `a=1, b=-1` (want 0): - In 32-bit 2s complement: a=0x00000001, b=0xFFFFFFFF. - Iteration 1: carry = (1 & 0xFFFFFFFF) << 1 = 2. a = 1 ^ 0xFFFFFFFF = 0xFFFFFFFE. b = 2 & 0xFFFFFFFF = 2. - Iteration 2: carry = (0xFFFFFFFE & 2) << 1 = 4. a = 0xFFFFFFFE ^ 2 = 0xFFFFFFFC. b = 4. - ... this continues, with the carry rippling left. Eventually b becomes 0 and a becomes 0x00000000. - `a = 0 <= MAX`, so return 0. Correct. **Converting back to a signed int:** if `a > MAX` (bit 31 is set), the 32-bit pattern represents a negative number. The expression `~(a ^ MASK)` flips the top 32 bits and then flips all bits, which correctly converts the unsigned 32-bit pattern to the equivalent negative Python integer. Alternatively, `a - (MASK + 1)` also works (but uses subtraction, which is disallowed here). **Common mistakes:** - Not masking in the loop body for Python: the carry can grow without bound. - Forgetting to check the sign bit at the end: Python arbitrary-precision integers will represent the 32-bit 2s complement value as a large positive number if you do not reinterpret it. **Interview note:** in most languages (Java, C++), this problem is straightforward because integers are already 32-bit fixed-width. In Python you must apply the masking trick. If the interviewer asks why, explain that Python uses arbitrary-precision integers and that simulating 32-bit overflow requires the masking approach above.

Sum of Two Integers

Example 1

Example 2

Constraints