(JAVA) Simple 0ms iterative loop with clear and concise explanation!


  • 1

    Use the "carry" variable to get all indices where a + b would overflow, aka when both bits are "1". Because we use AND, this variable will only contain "1" in places where a and b both have "1".

    Add a and b together using XOR, which produces the same result as a + b, EXCEPT for overflows (since 1 ^ 1 = 0).

    But since you have stored all the overflows in the "carry" variable, you can just shift left one and then add the overflows to the next highest bit place in the same way.

    Repeat until there is nothing left to carry. This is the same as a + b, with all carry bits distributed.

    public int getSum(int a, int b) {
        int carry = 0;
        while(a != 0) {
            carry = (a & b);
            b = b ^ a;
            a = carry << 1;
        }
        return b;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.