One liner with detailed explanation


  • 30
    S

    The chosen answer from this post: adding-two-numbers-without-operator-clarification helps me understand how it works, and recursion proves to be more intuitive to me than iterative.
    Basically, with key points:

    1. exclusive or (^) handles these cases: 1+0 and 0+1
    2. AND (&) handles this case: 1+1, where carry occurs, in this case, we'll have to shift carry to the left, why? Think about this example: 001 + 101 = 110 (binary format), the least significant digits of the two operands are both '1', thus trigger a carry = 1, with this carry, their least significant digits: 1+1 = 0, thus we need to shift the carry to the left by 1 bit in order to get their correct sum: 2

    My initial submission with inspiration from that post:

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

    Then I found the above solution could be shortened to one-liner:

    public int getSum(int a, int b) {
        return b == 0 ? a : getSum(a^b, (a&b)<<1);
    }
    

  • 1
    F

    I have a NON-RECURSIVE one-liner:

    int getSum(int a, int b) {while (b=(~(a^=b)&b)<<1); return a;}

  • 1

    clever use of '~'.


  • 0

    @steve.j.sun How to explain the corner case b==0?


  • 0

    @kobe When the carry is done(keeping shifting left until 0), the sum itself is the expected result.


Log in to reply
 

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