(Leetcode) 371 - Sum of Two Integers
1월 31일날 문제를 풀고 2월 9일인 이제서야 정리를 하게 되었다.
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
이 문제는 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 값(더하면서 발생된 올림 수)을 보관하게 된다.
이후 만약 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)만큼 반복문이 진행된다.