[位运算] XOR 异或 ^ NOT AND

[Linjiayu6]

1 - 136. 只出现一次的数字 (除了某元素出现1次外其他均出现2次)

要求: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

---

XOR 异或运算 P=A⊕B

相同数为0  不同为1
eg: 001 ^ 101 (1 和 5) => 100(5)

任何数 和 0异或是本身
eg: 000 ^ 101 (0 和 5) => 101(4)  => **0 ^ x = x**

相同的数 两两异或，是为0
eg: **x ^ x = 0**

# 输入: [2,2,1]  输出: 1
class Solution(object):
    def singleNumber(self, nums):
        """
        每个数都和0异或, 如此往复选出 只出现一次的值
        [2,2,1] => [010, 010, 001]
          1. 000 ^ 010 = 010
          2. 010 ^ 010 = 000
          3. 000 ^ 001 = 001 最后选出来为1
        """
        value = 0
        for num in nums:
            value = value ^ num # 位运算
        return value # 选出来的唯一值

[Linjiayu6]

运算总结

XOR 异或运算 P=A⊕B

相同数为0  不同为1
eg: 001 ^ 101 (1 和 5) => 100(5)

任何数 和 0异或是本身
eg: 000 ^ 101 (0 和 5) => 101(4)  => **0 ^ x = x**

相同的数 两两异或，是为0
eg: **x ^ x = 0**

& 与运算 (同时为1才为1, 否则为0)

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

与运算的作用:
1. 清零。00000 & 11011 = 00000
2. 取指定位。X = 10101110，我们想取后4位。
    所以 X & 00001111 = 00001110 这样得到后四位

| 或运算 (有1就是1, 全0为0)

或运算作用:
1. 某些位置置1.
X = 1010 0000, 我们想后四位置为1 X or 0000 1111 = 1010 1111

~ 取反运算 (0变1 1变0)

X = 001
~X = 110

<< 左移运算符

如果最右侧高位待舍弃位数不是1，则每次左移一位，相当与该数乘以2。

X = 001
X= X << 1 => 010 二进制左移动1位, 右侧补0
X= X << 2 => 100 二进制左移动两位, 右侧补0

* 如果最右侧高位待舍弃位数不是1，则每次左移一位，相当与该数乘以2。
- 0001 = 1
=> 0001 << 1 => 0010 = 2
=> 0001 << 2 => 0100 = 4
=> 0001 << 3 => 1000 = 8

正数5 => 101
负数5 => 11111111111111111111111111111011    (取反+1为正数5)

11111111111111111111111111111011 << 2 = 11111111111111111111111111101100 (= -20)

>> 右移运算符

每次向右移动，相当于除以2。 1342. 将数字变成 0 的操作次数

右侧丢弃1，正数左侧补0，负数左侧补1
X = 1000 =8
X >> 1 => 0100 => 8 / 2= 4

- 10 => 11111111111111111111111111110110
11111111111111111111111111110110 << 2 = 11 111111111111111111111111111101
右侧补了两个11, 后面舍弃了两位

[Linjiayu6]

2 - 137. 只出现一次的数字 II (除了某元素出现1次外其他均出现3次)

• 除了1个不一样，其他数字均是出现2次
• 出现三个一样的数字 或 5个 ...... 奇数个数，异或结果是自己
• 除了1个不一样，其他数字均出现3次? 怎么办?

思路:

• 有3个数一样，则二进制计算1出现的个数为 3的倍数。余数为0
• 有3个数一样 + 1一个不同，则统计出现1的次数，每个位再余数，就是最后挑出来的值。

结论: 
one = one ^ n & ~two
two = two ^ n & ~one

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

最后返回0 参考来自

# 独立想出来的 利用字典判断 + 两次相同异或区分值
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

[Linjiayu6]

3 - 371. 两整数之和

(异或 - 无进位结果, 与运算 - 进位位置说明 + 左移位)

例如: 3 + 4 = 7 无进位标识，返回异或结果即可

例如: 3 + 4 = 8 异或结果 + 进位结果 => 进位结果左移位 << 1 直到进位为0结束

1. a, b 两个数
2. xor = a ^ b 异或运算
3. carry = a and b 与运算 
    if 当与运算结果为0, 
        return 则直接返回 xor
    else 
       说明有进位运算,  需要将进位全部处理置为0才结束。
        carry = carry << 1 例如第一个位置为1， 说明1是作用在第二个位置上的。所以左移一位。
        b = carry 
        a = xor

4.  继续a 和 b的运算 . .....

// 第一版
var getSum = function(a, b) {
    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
};

// 第二版
/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var add = function(a, b) {
    // 异或运算
    xor = a ^ b
    and = (a & b) << 1
    if (and === 0){
        return xor
    }
    return add(xor, and)
};

在 Python 中，整数不是 32 位的，也就是说你一直循环左移并不会存在溢出的现象，这就需要我们手动对 Python 中的整数进行处理，手动模拟 32 位 INT 整型。 详见

# 这个不完全对
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

[Linjiayu6]

4 - 面试题15. 二进制中1的个数 与运算判断 + >> 1 右移位

同191. 位1的个数

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

[Linjiayu6]

5 - 剑指 Offer 56 - I. 数组中数字出现的次数

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]