Share my solution using "XOR" and "AND"


  • 4

    The Problem is a simple carry-adder question in digital circuit;

        class Solution {
        public:
            int getSum(int a, int b) {
        		int carry=a&b;
        		int result=a^b;
        		while(carry!=0){
                   		int carry_t=carry<<1;
    			carry=carry_t&result;
        			result=result^carry_t;
        		}
        		return result;
            }
        };
    

    However, I wonder is there anybody write it in carry-lookahead adder...


  • 0
    Y

    Your solution is awesome, but I am kind of confused, could you please kindly explain it in details? Thanks very much.


  • 0

    @ycl11761
    Sorry about replying this so late....
    The system of leecode discuss has changed and I miss the notification... Sorry! qAq

    you can read the definition of adder in https://en.wikipedia.org/wiki/Adder_(electronics)

    so,for every bit in an integer:
    (1)we can calculate the carry-bit by doing &(AND) operation.because only 1+1=10 is carried;
    (2) we calculate the left-bit by doing ^(XOR) operation. because 1+1=0 (ignored the carry-bit) 0+0=0, 1+0=1 0+1=1;
    all the carry-bits in (1) together form an new integer: int carry,
    all the left-bits in (2) together form an new integer: int result
    we see this two integer as two new integer and repeat the (1) and (2)step to get their sum until carry is 0.
    Hope this is not too late.


  • 0

    I find it easy to understand while two numbers are both non-negative.
    Your solution also works for negative situation, but I have no clue how.
    Do you have an easy way to think about?


  • 2

    @clydexu
    This can work in negative situation since that carry-adder also works in Two's complement.
    If you think:
    -2=1000 0000 0000 0000 0000 0000 0000 0010
    then:
    -2+-2=0000 0000 0000 0000 0000 0000 0000 0100=4 (WTF?)
    The solution is wrong.
    However, negative numbers are stored in Two's complement to ensure that -0=0.
    Such that:
    -2=1111 1111 1111 1111 1111 1111 1111 1110
    Then
    -2+-2=
    1111 1111 1111 1111 1111 1111 1111 1100=-4
    (or in detailed:
    in 1st round,
    result=0000 0000 0000 0000 0000 0000 0000 0000
    carry=1111 1111 1111 1111 1111 1111 1111 1110(because -2 & -2=-2)
    carry_t=1111 1111 1111 1111 1111 1111 1111 1100(the most left bit has been dropped)
    in the 2nd round,
    result=1111 1111 1111 1111 1111 1111 1111 1100=-4
    carry=0
    )
    Hope you can get it right, and give me and up-vote~~ : )


  • 0
    J
        def getSum(self, a, b):
            """
            :type a: int
            :type b: int
            :rtype: int
            """
            while b != 0:
                carry = (a & b) << 1
                a ^= b
                b = carry
            return a
    
    

    I submit this problem with python, but get TLE with test case: a = -1 and b = 1,


  • 0

    @JCKoala_py
    I am not familiar with python...
    But I think this is caused by python's int is not 32 bit length.
    in c++, a or b will just left shift to sth. like 1000 0000 0000 0000 0000 0000 0000 0000 and then go to zero.
    I guess in python we dont have the time waiting it turns to zero.
    I think you can fix it by just adding

    if a==-b:
      return 0
    

    at the begining.
    You can say that this is a kind of bug of my code...>_<
    Again, I am not familiar with python, nice try for writing it into python.
    Hope you can get it right, and give me a thumbs-up~~ : )


Log in to reply
 

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