One liner with detailed explanation


  • 29
    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?


Log in to reply
 

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