Sum of Two Integers
Add without `+` — XOR is sum without carry; AND-shifted is the carry; loop until carry is zero.
2 min read
bit-manipulation math
Problem#
Return a + b without using + or -.
Examples#
a=1, b=2→3.a=2, b=3→5;a=-2, b=3→1.
Constraints#
-1000 <= a, b <= 1000.
Approach#
XOR is the bitwise sum (no carry). AND then left-shift by 1 is the carry. Loop: sum = a ^ b; carry = (a & b) << 1; a = sum; b = carry until b == 0. Use unsigned to avoid undefined left-shift on negative.
Solution#
class Solution {public: int getSum(int a, int b) { unsigned ua = a, ub = b; while (ub != 0) { unsigned carry = (ua & ub) << 1; ua = ua ^ ub; ub = carry; } return (int)ua; }};func getSum(a int, b int) int { ua, ub := uint32(a), uint32(b) for ub != 0 { carry := (ua & ub) << 1 ua = ua ^ ub ub = carry } return int(int32(ua))}class Solution: def getSum(self, a: int, b: int) -> int: mask = 0xFFFFFFFF ua, ub = a & mask, b & mask while ub != 0: carry = ((ua & ub) << 1) & mask ua = (ua ^ ub) & mask ub = carry # interpret as signed 32-bit if ua >= 0x80000000: return ua - (1 << 32) return uavar getSum = function(a, b) { while (b !== 0) { const carry = (a & b) << 1; a = a ^ b; b = carry; } return a;};class Solution { public int getSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; a = a ^ b; b = carry; } return a; }}function getSum(a: number, b: number): number { while (b !== 0) { const carry: number = (a & b) << 1; a = a ^ b; b = carry; } return a;}Editorial#
Two’s complement makes this work uniformly for negative numbers — the overflow at bit 31 naturally implements the negative arithmetic. Using unsigned avoids C++ undefined behavior for left-shifting a 1 into the sign bit.
Complexity#
- Time:
O(log max(|a|, |b|)). - Space:
O(1).
Concept revision#
Related#