[NeetCode-LeetCode] Sum of Two Integers JAVA

반응형

728x90

[NeetCode-LeetCode] Sum of Two Integers - Medium

---

접근

• 비트 조작

---

풀이

단순하게 두 수를 더하는 문제인데 +, - 연산자를 사용하지 않고 두 수의 합을 구하는 문제이다. 즉 비트 연산자를 사용해 덧셈을 구현하면 되는 문제이다. 

 

간단하게 생각하면 비트 연산으로 더하기가 되려면 1과 0이 만나면 1이 되어야 하고 1과 1이 만나면 0, 0과 0이 만나도 0이 되어야 한다. XOR을 쓰면 정확하게 두 비트가 다른 경우에만 1이 되기 때문에 더하기 과정을 구현할 수는 있다. 그러나 단순하게 XOR 연산만 수행하다 보면 올림 처리된 즉 캐리가 발생하는 경우 캐리에 대한 처리가 이루어지지 않는다. 

//캐리가 발생하지 않는 덧셈
1 + 2 = 01 ^ 10 = 11 = 3 -> 정상 값

//캐리가 발생하는 덧셈
2 + 2 = 10 ^ 10 = 00 = 0 -> 올바르지 않은 값

위와 같이 캐리 처리를 하지 않아 단순 자릿수 덧셈만 발생하기 때문에 올바른 값이 나오지 않는다. 올바른 결과를 구하기 위해선 캐리가 0이 될 때까지 덧셈한 값에 캐리를 더해주는 과정을 수행해야 한다. 캐리를 구하는 방법은 AND 연산을 통해 두 비트가 1인 경우를 구하고 왼쪽으로 1비트 시프트 해주게 되면 구할 수 있다.

//캐리 처리 과정 포함
덧셈: 2 ^ 2 = 10 + 10 = 00
캐리: 2 & 2 = 10 << 1 = 100

합 + 캐리 = 00 + 100 = 100 = 3

위와 같이 XOR 연산과 캐리를 더해주면 올바른 값이 나오게 되는데 캐리와 XOR 값을 더하는 과정에서 또 캐리가 발생할 수 있기 때문에 캐리가 0으로 발생하지 않을 때까지 수행해줘야 한다. 

    public int getSum(int a, int b) {
        while (b != 0) {
            int sum = a ^ b;
            
            int carry = (a & b) << 1;
            
            a = sum;
            b = carry;
        }
        
        return a;
    }

 

---

전체 코드

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