Recursive C++ solution with step by step explanation


  • 1
    X

    It takes me a lot of time to understand the solution.
    So I decide to share my thought, and I hope this can help someone.

    Assume a = 1 = 1, b = 7 = 111, and you want to do a + b in binary form. Intuitively, you will add them bit by bit and get the carry, like this

    carry-----1 1
    a-------------1
    b---------1 1 1
    sum---1 0 0 0

    But how about adding all the bits at the same time?

    Firstly, ignore the carry, add all the bits and store the result.
    But how to add without using +? Observe 0+0=0, 0+1=1, 1+0=1, 1+1 = 0, that's XOR.
    So we have sum = a ^ b.

    Secondly, get the carry for all the bit. Once again, observe 0+0 => carry = 0, 0+1 => carry = 0, 1+0 => carry = 0, 1+1 => carry = 1, that's AND. And you need to left shift the carry by 1, just like what you do of bit by bit add.
    So we have carry = (a & b) << 1.

    Then we can get the result by getSum(sum, carry), here is an example

    a = 1 = 1, b = 7 = 111
    sum = 1 ^ 111 = 110
    carry = (1 & 111) << 1 = 10

    So we get the first step of addition, and we can get the answer by calling getSum(sum, carry) recursively, just like manual addition.

    But what's the end condition?
    Think about the question, when should we end the manual addition?
    The answer is no more carry exists.

    So we have the recursive algorithm. And you can rewrite it in an iterative way if you have this recursive version.

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

Log in to reply
 

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