[位运算] XOR 异或 ^ NOT AND about leetcode HOT 5 OPEN

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            ones = ones ^ num & ~twos
            twos = twos ^ num & ~ones
        return ones

# 独立想出来的 利用字典判断 + 两次相同异或区分值
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 字典用来过滤 第一次 xor 第二次出现不操作 第三次出现操作
        dictionary = {}
        nums.sort()
        result = 0
        for i in nums:
            if i in dictionary:
                if dictionary[i] == 2: 
                    result = result ^ i
                dictionary[i] += 1
            else:
                dictionary[i] = 1
                result = result ^ i
        
        return result

# 这个不完全对
class Solution:
    def getSum(self, a: int, b: int) -> int:
        if a == 0: return b
        if b == 0: return a
        while b !=0:
            xor = a ^ b
            carry = a & b
            if carry == 0: return xor
            carry = carry << 1
            a = xor
            b = carry
        return a

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n != 0:
            if n & 1 == 1: count +=1 # 与操作1 & 1 = 1, 0 & 1 = 0
            n = n >> 1 # 右移一位
        return count

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        if len(nums) == 2:
            if nums[0] != nums[1]: return nums
        nums.sort() # 排序

        half = len(nums) // 2
        left, right = nums[0: half], nums[half:]

        left_val, right_val = 0, 0
        for i in left: left_val = left_val ^ i
        for i in right: right_val = right_val ^ i

        # 值在right里面
        if left_val == 0: return self.singleNumbers(right)
        # 值在left里面
        if right_val == 0: return self.singleNumbers(left)
        # 值在左右两侧, 如果奇数个数 [1, 2, 2, 3, 3, 5] return [1, 5]
        if len(left) % 2 == 1: return [left_val, right_val]
        # 如果是 [1,2, 2, 4] 则需要这样处理
        data = 0
        for j in range(1, len(right)): data = data ^ right[j]
        return [left_val ^ right[0], data]