A simple 3-line solution with bit manipulation and recursion


  • 0
    H

    Explanation

    Imagine we are doing addition in binary. We can break it into 3 parts:

    • calculate every bit correspondingly and find what remains
    • if it exceeds, bring it to next bit as a carry
    • add remain and carry, which we can do recursively

    For example,

    7 + 5 =

    0 0 1 1 1
    0 0 1 0 1
    ----------
    0 0 0 1 0 -----> remain = a xor b
    0 1 0 1 0 -----> carry = (a and b) << 1
    ---------- -----> another addition
    0 1 0 0 0
    0 0 1 0 0
    ----------
    0 1 1 0 0

    So answer is pretty trivial, we do first 2 steps and invoke the method again using the results of previous steps as arguments.

    Solution

    Here is the code

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

Log in to reply
 

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