Share my C++ solutions,easy to understand


  • 51
    V
    class Solution {
    public:
        int getSum(int a, int b) {
            int sum = a;
            
            while (b != 0)
            {
                sum = a ^ b;//calculate sum of a and b without thinking the carry 
                b = (a & b) << 1;//calculate the carry
                a = sum;//add sum(without carry) and carry
            }
            
            return sum;
        }
    };

  • 7
    V

    Calculate step by step:

    class Solution {
    public:
        int getSum(int a, int b) {
            if (a == 0)
                return b;
            if (b == 0)
                return a;
                
            int sum = 0;
            int mask = 1;
            int  c = 0;
            
            while (mask != 0)
            {
                int m1 = (a & mask) != 0 ? 1 : 0;
                int m2 = (b & mask) != 0 ? 1 : 0;
                
                if (m1 == 1 && m2 == 1)
                {
                    if (c == 1)
                        sum |= mask;
                    
                    c = 1;
                }
                else if ((m1 ^ m2) == 1)
                {
                    if (c == 1)
                        c = 1;
                    else
                        sum |= mask;
                }
                else
                {
                    if (c == 1)
                    {
                        sum |= mask;
                        c = 0;
                    }
                }
                
                mask <<= 1;
            }
            
            return sum;
        }
    };

  • 0
    L

    talented !!!


  • 0
    D

    Is this also working with negative cases? Why?


  • 2
    V

    Yes. Because it simulates the process of addition in computer.


  • 1
    S

    why the carry always be zero at last?


  • 2
    Z

    Just a brief Proof why this loop will end within O(logn):

    • We definte card(n) to be the count of 1s in n's binary representation.
    • by the end of each loop, card(sum) <= min(card(a), card(b)), and the equal sign will only happens when a = b. (think about xor op)
      • So if a != b, card((a & b) << 1) < min(card(a), card(b))
      • If a == b, sum in next loop will be 0, and b will be 0 then, and While will end in 1 extra loop. i.e. this will only happen at the last loop.

    So combining the previous, while loops at most O(logn) times.


  • 1
    D

    Easy to understand? Please give a proof!


  • 0
    I

    Not easy to understand...


  • 0
    S

    @shenrf22 loop until carry part is 0, each loop sum of a, b is not change, his idea is excellent


  • 0
    S
    int addition(int a,int b)  
    {  
        if(b == 0)  
            return a;  
        return addition(a^b,(a&b)<<1);  
    }  
    

    This is a good idea, but it cannot pass the complie.(


  • 0
    A

    @vdvvdd I have the same question as shenrf22 , why is b zero at last?


  • 0
    M

    awesome,excellent.


  • 0
    X

    @ziyangqi Hi, if a=111000, b=000111, so sum=a^b=111111, then b=(a&b)<<1=0, a=sum=111111, is card(sum)<=min(card(a), card(b)) in this loop true?


  • 0
    C

    +1 for Calculate step by step


  • 0
    Z

    @xinyufeng16 Sorry, there was a typo, in the that line. It should be

    • So if a != b, card((a & b) << 1)
      Rather than
    • So if a != b, card(sum)
      I've updated the proof.

Log in to reply
 

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