C++ solution, 0ms, don't have to check for sign, has comments.


  • 1
    R
    class Solution {
    public:
        int getSum(int a, int b) {
            // Take 1 + 2 for example in 4 bits.
            // Same as 0001 + 0010
            // Binary addition requires going through each bit position and
            // generating a carry in bit, carry out bit and sum bit.
            // For example, in bit position 0 in 0001 + 0010, 
            // carry in: 0, sum bit: carry in + 1 + 0 = 1, carry out: 0
            // For bit position 1,
            // carry in: 0, sum bit: carry in + 0 + 1 = 1, carry out: 0
            // Using a truth table, we can figure out that
            // sum bit = carry in xor bit_a xor bit_b.
            // carry out = (carry in AND bit_a) OR (carry in AND bit_b) OR (bit_a AND bit_b)
            // carry out becomes the carry in for the next bit position.
            int result = 0x0;
            int sum_bit = 0x0;
            int carry_bit = 0x0;
            int bitmask = 0x1;
            int bit_a = 0x0;
            int bit_b = 0x0;
            
            int i = 0;  // Keep track of what bit position im in.
            while (bitmask != 0x0) {
                // Isolate bits in each bit position.
                bit_a = (a & bitmask) >> i;
                bit_b = (b & bitmask) >> i;
                
                // Calculate sum, carry_bit is a carry in now.
                sum_bit = ((carry_bit ^ bit_a) ^ bit_b);
                // Shift sum_bit to correct bit position, OR into result.
                result |= (sum_bit << i);
                // Calculate carry out, carry_bit is now a carry out after calculation.
                carry_bit = ((bit_a & bit_b) | (carry_bit & bit_a)) | (carry_bit & bit_b);
                
                // Shift bitmask over 1 to the left.
                bitmask <<= 1;
                // Increment bit position.
                ++i;
            }
            return result;
        }
    };
    

Log in to reply
 

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