이 흑 마법 비트 단위가 작동하는 이유는 무엇입니까?

비트별 xor는 비트가 다르면 1이고, 비트가 같으면 0입니다.
예를 들어(여기서 D는 10진수이고 B는 2진수임), 20D == 10100B 및 9D = 1001B:

10100
1001


11101
및 11101B == 29D.

하지만, 캐리가 있는 케이스가 있다면 그렇게 잘 작동하지 않습니다. 예를 들어 20D와 20D를 추가(비트 xor)하는 것을 고려하십시오.

10100

10100

00000
이런. 20 + 20은 확실히 0과 같지 않습니다. (a & b) << 1 항을 입력하십시오. 이 용어는 각 포지션에 대한 "캐리"를 나타냅니다. while 루프의 다음 반복에서 이전 루프의 캐리를 추가합니다. 따라서 이전에 사용했던 예제를 사용하면 다음과 같은 결과를 얻습니다.

첫 번째 반복(a는 20, b는 20)

10100 ^ 10100 == 00000 # 0이 됨
(10100 & 10100) << 1 == 101000 # b를 40으로 만듭니다.

두 번째 반복:

000000 ^ 101000 == 101000 # 40이 됩니다.
(000000 & 101000) << 1 == 0000000 # b를 0으로 만듭니다.
이제 b는 0이고 끝났으므로 a를 반환합니다.

이 알고리즘은 내가 설명한 특정 사례에 대해서만 아니라 일반적으로 작동합니다. 정확성에 대한 증명은 연습으로 독자에게 맡깁니다 ;)

Python 솔루션(가장 찬성)

def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        MAX_INT = 0x7FFFFFFF
        MIN_INT = 0x80000000
        MASK = 0x100000000
        while b:
            a, b = (a ^ b) % MASK, ((a & b) << 1) % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)

마스크는 무엇을 합니까?

코드에 a, b 및 반환 유형이 int 유형이라는 주석이 있기 때문에 마스크가 수행하는 모든 작업은 값이 정수인지 확인하는 것입니다. 따라서 가능한 최대 int(32비트)는 2147483647입니다. 따라서 예제에서와 같이 이 값에 2를 더하면 int가 오버플로되어 음수 값을 얻게 됩니다. Java 및 C++와 같은 다른 강력한 유형의 언어가 정의한 이 int 경계를 존중하지 않기 때문에 Python에서 이를 강제해야 합니다. 다음을 고려하세요:
def get_sum(a, b):
while b:
a, b = (a ^ b), (a & b) << 1
return a
This is the version of getSum without the masks.
_print get_sum(2147483647, 2)
출력

2147483649
동안

인쇄 솔루션().getSum(2147483647, 2)
출력

-2147483647
오버플로로 인해.
_
이야기의 교훈은 int 유형을 32비트만 나타내도록 정의하면 구현이 정확하다는 것입니다.