[LeetCode] 371. Sum of Two Integers

Sum of Two Integers - LeetCode

Binary operation을 사용하는 기본 문제라고 한다.

 

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:
Input: a = 1, b = 2 Output: 3

Example 2:
Input: a = 2, b = 3 Output: 5

첫 시도

하지만 역시 또 time limit에 걸려버렸다. 역시 나야!

class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b != 0:
            _and = a & b
            _xor = (a | b) & ~_and

            a = _xor
            b = _and << 1
        return a

 

두 번째 시도

다른 답안을 보니 이렇게 하란다... 설명하는 내용을 보면 기본적인 것은 내가 했던 것과 비슷하다.

 

To solve the problem of summing two integers without using the + or - operators, we can utilize bitwise operations. The key is to understand how binary addition works:

• The XOR (^) operation gives the sum without carrying over.
• The AND (&) operation identifies where the carry occurs.
• Shifting the carry by one bit (<<) simulates carrying over to the next significant bit. We repeat this process until there are no more carry operations left.

하지만 구체적인 접근 방식에서 큰 차이가 있었다. 음수에 대한 처리도 필요했기 때문

• Use a 32-bit mask (0xFFFFFFFF) to handle negative numbers and simulate a 32-bit integer.
• Perform the addition using XOR for the sum and AND for the carry.
• Shift the carry by one position to the left.
• Update the operands with the new sum and carry.
• Repeat until the carry becomes zero.
• Adjust for negative numbers if the result exceeds the maximum 32-bit integer.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF  # 32 bit mask
        maxInt = 2**31 - 1

        while b != 0:
            sum = (a ^ b) & mask # contain to 32 bits
            carry = (a & b) & mask # contain to 32 bits
            a = sum
            b = carry << 1
        
        return a if a <= maxInt else ~(a ^ mask)

 

왜 mask = 0xFFFFFFFF를 계속 and 처리해야 하는 지 모르겠어서 찾아보니 다음과 같은 답변을 찾았다.

 

Python의 정수는 무한 길이를 지원하므로, a ^ b나 a & b 연산 결과는 32비트를 넘어갈 수 있습니다.
하지만 이 함수는 32비트 정수를 가정하고 동작합니다.
& mask는 32비트 범위를 유지하기 위해 불필요한 상위 비트를 제거하는 역할을 합니다.

예를 들어:
-1은 Python에서 내부적으로 무한한 1의 연속(...1111111111111111)으로 표현되지만,
32비트에서는 0xFFFFFFFF로 표현됩니다.
비트마스크를 적용하지 않으면 이 차이 때문에 계산이 잘못됩니다.

 

즉, python 기능 때문에 32bit로 제한하려면 mask를 도입해서 길이 제한을 계속 해야한다는 뜻...

갈 길이 멀다...