371. Sum of Two Integers

Description:

Given two integers a and b, return the sum of the two integers without using the operators + and -.

 

/*
[1] full-adder)

idea::
using full-adder approach. bit-manipulation

code::
(below)

-T/C: O(32) =O(1). # regardless a and b, iterate 32times
-S/C: O(1)

[2] int to string)

idea::
int -> string -> add -> return

*/
    

class Solution {
    public int getSum(int a, int b) {
        int output=0;
        
        int carry=0;
        for(int i=0;i<32;++i){
            int a_prime=(a>>i)&1;
            int b_prime=(b>>i)&1;
            
            int sum=a_prime^b_prime^carry;
            carry=a_prime&b_prime | b_prime&carry | a_prime&carry;
            
            output=(sum<<i)|output;
        }
            
        return output;
    }
}