動機

當初是自幹加法器與2補數… 該學會用bit operation了，這操作太神啦!!

Problem

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

 

Example 1:

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

Example 2:

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

 

Constraints:

  • -1000 <= a, b <= 1000

2的補數

就是讓 n + ?? = 0 0與n的binary都是確定的，那麼??的binary是多少?

先退一步，如果加總的結果會把每個位元都轉成1的話，這樣我們以此再加1是不是就是0了!!

0001 + 1111 = (1)0000

所以??是n的not加1，有辦法用算數的方式得到補數嗎?

如果把10000減掉0001就是-1， 所以把2^(bits+1)-val就是補數

正數的最大值(最小的負數)在哪? ?? + ?? = (1)0000 ??等於1000，也就是2^bits-1

所以如果遇到大於等於2^bits-1的數字要轉成負數，val-2^bits

Sol

def twos_complement(val, nbits):
    """Compute the 2's complement of int value val"""
    if val < 0:
        val = (1 << nbits) + val
    else:
        if (val & (1 << (nbits - 1))) != 0:
            # If sign bit is set.
            # compute negative value.
            val = val - (1 << nbits)
    return val
def adder(a,b):
    a = int(a)
    b = int(b)
    return [a ^ b, a & b]
class Solution:
    def getSum(self, a: int, b: int) -> int:
        a = twos_complement(a,33)
        b = twos_complement(b,33)
        
        #print(format(a,'b').zfill(33),format(b,'b').zfill(33))
        a = iter(reversed(list(format(a,'b').zfill(33))))
        b = iter(reversed(list(format(b,'b').zfill(33))))
        
        c = []
        carry = 0
        for _ in range(33):
            aa = next(a)
            bb = next(b)
            tmp, cc1 = adder(aa,bb)
            s, cc2 = adder(tmp, carry)
            carry = cc1 | cc2
            c.append(s)
        c.reverse()
        #print(c)
        c = ''.join(str(tmp) for tmp in c)
        #print(c)
        c = twos_complement(int(c,2),33)
        return c

Case Study

1與1相會要進位，用and加左移來模擬 01,01都會變成1，00,11都要變成0，這就只能是xor了

所以就是上面的步驟反覆做直到沒有可以進位的數為止，太神啦!!!

class Solution(object):
    def getSum(self, a, b):
        # 32 bits integer max
        MAX = 0x7FFFFFFF
        # 32 bits interger min
        MIN = 0x80000000
        # mask to get last 32 bits
        mask = 0xFFFFFFFF
        while b != 0:
            # ^ get different bits and & gets double 1s, << moves carry
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        return a if a <= MAX else ~(a ^ mask)