1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

'''
1. 덧셈 기호를 사용하지 않고 두 정수의 덧셈을 하는 문제.

2. XOR, AND 비트연산으로 덧셈을 구현할 수 있다. XOR 연산은 덧셈 시 각 자릿수가 갖는 값과 같은 값을 리턴하고,
   AND 연산은 덧셈 시 그 자릿수에서 자리올림이 발생하는지를 알려준다. 자리올림이 나타날 때마다 XOR 연산을 반복해,
   더 이상 자리올림이 나타나지 않을 때까지 루프를 수행한다.

3. 위 연산 방법은 덧셈 하려는 두 수가 모두 양수거나 모두 음수거나 음수쪽이 양수쪽보다 절대값이 더 큰 경우에만
   정상적으로 작동하며, 음수쪽이 양수쪽보다 절대값이 더 작은 경우에는 정상적으로 작동하지 않고 자리올림수가
   무한히 커지는 모습을 보인다. 따라서 이 경우에는 예외적으로 비트연산으로 뺄셈을 구현해 처리했다.

   뺄셈 또한 XOR, AND 비트연산으로 구현할 수 있다. XOR 연산의 결과값은 뺄셈 시 각 자릿수가 갖는 값과도 일치한다.
   한편, 뺄셈 시 자릿수 내림 유무는 어느 한 쪽 수의 1의 보수와 다른 쪽 수의 AND 연산을 통해 알 수 있다.
   자릿수 내림이 나타날 때마다 XOR 연산을 반복해, 더 이상 자릿수 내림이 나타나지 않을 때까지 루프를 수행한다.

   프로그래밍 언어는 음수를 2의 보수를 통해 표현하므로, 사실 덧셈과 뺄셈의 비트연산을 통한 구현은 1의 보수와
   2의 보수의 차이에 불과하다. 다만 2의 보수를 사용하는 방법이 무한 루프를 발생시키는 경우가 있는 것인데,
   이 경우 1의 보수를 사용함으로써 극복할 수 있는 것이다.
'''
   

def plus(a, b):
    while b:
        carry = (a & b) << 1
        a ^= b
        b = carry
    return a

def minus(a, b):
    while b:
        borrow = ((~a) & b) << 1
        a ^= b
        b = borrow
    return a

class Solution:
    def getSum(self, a: int, b: int) -> int:
        if a * b > 0: return plus(a, b)
        else:
            if a > b: a, b = b, a
            if -a > b: return plus(a, b)
            else: return minus(b, -a)