[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;
    }

 

 

 

코드

	class Solution {
	public:
	const static int max_bit = 10;
	//양수와 음수를 더하는 경우
	static 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;
	}
	//같은 부호의 값끼리 더하는 경우
	static 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 getSum(int a, int b) {
	int answer = 0;
	if (a < b)
	swap(a,b);
	if (b < 0 && a>0)
	answer = SumPosNeg(a,b);
	else {
	if (a <= 0) {
	a *= -1; b *= -1;
	answer = SumSame(a, b);
	answer *= -1;
	}
	else {
	answer = SumSame(a, b);
	}
	}
	return answer;
	}
	};

view raw Sum of Two Integers.cpp hosted with ❤ by GitHub