박종훈 알고리즘 블로그

(Leetcode) 371 - Sum of Two Integers

1월 31일날 문제를 풀고 2월 9일인 이제서야 정리를 하게 되었다.

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


Sum of Two Integers

이 문제는 python에서 기본적으로 제공해주는 +- 를 사용하지 않고 연산을 처리해주면 되는 문제이다.

binary 연산을 통해서 해결할 수 있다.

최종 코드는 다음과 같다.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MAX = 0x7FFFFFFF
        mask = 0xFFFFFFFF

        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask

        if a > MAX:
            a = ~(a ^ mask)

        return a

2의 보수

참고로 입력값들은 음수도 허용된다. 따라서 이 문제를 풀기 위해서는

와 같은 개념을 알아야 한다.

예시로 생각해보는 계산 과정

만약 a 가 217이고 b가 -318 이였다면 어떻게 될까? (이렇게 수를 정한 이유는 크게 없다. 무작위로 정했으며 2의 n승인 숫자는 피하려고 했다.)

차근차근 계산해보자.

  • ^ 는 xor 연산이다. 대응되는 비트가 서로 다르면 1을 반환한다.
  • & 는 and 연산이다. 대응되는 비트가 모두 1이면 1을 반환한다.
  • « 는 지정한 수 만큼 비트들을 왼쪽으로 이동시킨다. (shift left)
  • ~ 는 NOT 연산이다. 1의 보수를 반환 한다.
  • 예시로 정한 입력값에서 a는 양수고 b는 음수다. 따라서 bit 연산할 때 음수는 2의 보수 처리를 해줘야 한다.
  • a는 둘이 더해졌을 때의 값(carry 무시)을 b는 carry 값(더하면서 발생된 올림 수)을 보관하게 된다.

example2

이후 만약 a가 MAX 보다 크다면 음수인 것을 의미한다. 음수라면 다시 2의 보수를 취해줘야 한다.

a가 음수이기 때문에 a ^ mask 는 모든 수를 반전시킨다 (여기까지가 1의 보수)

~ 연산자가 알아보다보니 조금 묘했다. 공식문서에서는 다음과 같이 설명한다.

Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.

~ 연산자는 해당 값을 부호 비트를 바꾸고 1을 뺀것과 같은 효과를 준다. 이를 통해서 2의 보수가 될 수 있다.

python의 int 범위, python 의 음수 양수 처리 방식

python은 int의 범위가 unbound이다. python도 음수인지 양수인지 체크를 별도의 부호 비트를 사용한다. 따라서 C같은 언어처럼 int의 범위가 지정되어 있고 첫번째 비트를 사용하는 방식은 아니다.

이로인해 식 중간중간에 불필요 해보이는 ^ mask 가 들어가 있는 것이다. (32bit으로 제한해서 처리하기 위해)

참고

bit 연산자에 대한 설명은 FAQ: What do the operators <<, >>, &, |, ~, and ^ do?를 참고하면 좋을 것 같다.

자바로 다시 풀기 (240731)

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

    return a;
  }
}

TC, SC

시간 복잡도는 O(1), 공간복잡도는 O(1) 이다. 최악의 경우 b의 비트수(32)만큼 반복문이 진행된다.