Sum of Two Integers: the idea to remember.

The core insight

XOR computes the sum without carry. AND followed by a left shift computes the carry; repeat until it is zero.

Why it works

Each round resolves the current carry positions and pushes any remaining carry toward more significant bits. Java int overflow follows 32 bit two complement arithmetic.

The mistake to avoid

OR is not a carry free sum. Keep the carry in a temporary variable before updating either operand.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a ^= b; // Sum at positions that do not carry.
        b = carry;
    }
    return a;
}

Make the next connection