[LeetCode] 371. Sum of Two Integers (C++)

문제

 

https://leetcode.com/problems/sum-of-two-integers/

Sum of Two Integers - LeetCode

 

풀이

 

난이도: Medium 

 

어려운 문제라기보다는 비트 연산자를 잘 활용해서 구현을 해야 하는 문제이다.

 

같은 부호끼리의 합은 두 수를 양수로 고려하고 덧셈 후에 부호를 붙여주면 되기 때문에 같은 부호의 수를 더하는 함수와 다른 부호를 더하는 함수를 따로 구현하였다.

 

일단 같은 부호라면 두 수의 덧셈을 비트 연산으로 구현하면 되므로 비트의 올림을 고려하여 구현해 주면 된다.

c++에서는 true 는 1, false는 0으로 연산되는 점을 이용해 두 수의 해당 비트와 올림수 여부(ceil)를 확인해 구현해주었다.

 

int SumSame(int a, int b) {
        int answer = 0, n = 0;
        bool a_bit, b_bit, ceil = false;
 
        for (int bit_idx = 0; bit_idx <= max_bit; ++bit_idx) {
            a_bit = a & (1 << bit_idx);
            b_bit = b & (1 << bit_idx);
            n = ceil + a_bit + b_bit;
 
            ceil = false;
            switch (n)
            {
            case 1:
                answer |= (1 << bit_idx);
                break;
            case 2:
                ceil = true;
                break;
            case 3:
                answer |= (1 << bit_idx);
                ceil = true;
                break;
            default:
                break;
            }
        }
 
        if (ceil)
            answer |= (1 << (max_bit + 1));
 
        return answer;
    }

 

 

 

두 수가 다른 부호라면 부호를 제하고 내림 수를 고려하면서 뺄셈을 구현해 주면 된다.

    int SumPosNeg(int pos, int neg) {
        bool is_sum_pos = true;
        neg *= -1;
        if (pos < neg)
            is_sum_pos = false;
 
        if (pos < neg)    //항상 pos가 큰 값으로 유지
            swap(pos, neg);
 
        int answer = 0;
        bool pos_bit, neg_bit;
        for (int bit_idx = 0; bit_idx <= max_bit ; ++bit_idx) {
            pos_bit = (pos & (1 << bit_idx));
            neg_bit = (neg & (1 << bit_idx));
 
            if (pos_bit != neg_bit) {
                if (!pos_bit) {     //pos_bit =1, neg_bit = 0
                    for (int i = bit_idx + 1; i <= max_bit; ++i)
                        if (pos & (1 << i)) {
                            pos &= ~(1 << i);
                            for (int j = i - 1; j >= bit_idx + 1; --j)
                                pos |= (1 << j);
                        }
                    answer |= (1 << bit_idx);
                }
            }
        }
 
        if (!is_sum_pos)
            answer *= -1;
        return answer;
    }

 

 

 

코드