异或^

两个相等的数经过异或运算会相互抵消

通常用来删除偶数个相同的数字，保留基数个个数的数字

Swap Two Integers

不建议在实际应用中采用

1 不一定比朴素方法快
2 a 和 b 引用同一变量

void Swap(int &a, int &b)  
{  
    if (a != b)  
    {  
        a ^= b;  
        b ^= a;  
        a ^= b;  
    }  
}

389. Find the Difference

给定两个字符串s和t，都只包含小写字母。字符串t由字符串s打乱顺序并且额外在随机位置添加一个字母组成。寻找t中新增的那个字母。（和single number一样）

class Solution(object):
    def findTheDifference(self, s, t):
        res = 0
        n = len(s)
        for i in range(n):
            res ^= ord(s[i]) ^ ord(t[i])
        return chr(res ^ ord(t[n]))

268. Missing Number

给定一个包含从0, 1, 2, ..., n, 选出的n个不同数字的数组，从中找出数组中缺失的那一个数。这里是少了一个数，single number 是多了一个数。

class Solution(object):
    def missingNumber(self, nums):
        ret = 0
        for n in nums+range(len(nums)+1):
            ret ^= n
        return ret

136. Single Number

所有数字都出现偶数次，只有一个数字出现奇数次，求出现奇数次的那个数

解法1. HashSet

# Time : O(n), Space : O(n)
class Solution(object):
  def singleNumber(self, nums):
      numSet = set()
      for n in nums:
          if n in numSet:
              numSet.remove(n)
          else:
              numSet.add(n)
      return list(numSet)[0]

解法2.异或

# Time : O(n), Space : O(1)
# 偶数次异或可以抵消
class Solution(object):
  def singleNumber(self, nums):
      ret = 0
      for n in nums:
          ret ^= n
      return ret

137. Single Number II

所有数字出现三次，只有一个数字出现一次，求出现一次那个数。

解法1. HashTable

# Time : O(n), Space : O(n)
class Solution(object):
  def singleNumber(self, nums):
      dic = {}
      for n in nums:
          if n in dic:
              if dic[n] == 2:
                  del dic[n]
              else:
                  dic[n] += 1
          else:
              dic[n] = 1
      return dic.keys()[0]

解法2. 用二进制模拟三进制运算从一个bit出发考虑到32个bits

cnt  : 0    1    2     3          4
one  : 0 -> 1 -> 0 -> (1 -> 0) -> 1
two  : 0 -> 0 -> 1 -> (1 -> 0) -> 0
mask : 1    1    1     1    0

# Time : O(n), Space : O(1)
class Solution(object):
    def singleNumber(self, nums):
        one = two = 0
        for n in nums:
            two |= n & one
            one ^= n
            mask = ~(one & two)
            one &= mask 
            two &= mask
        return one

260. Single Number III

所有数字都出现两次，但是有两个数字只出现了一次。

a ^ a ^ b ^ b ^ c ^ d = c ^ d
0101 0100 c
1001 0010 d
1100 0110 c^d

把只出现一次的c和d分到两个组里

class Solution(object):
    def singleNumber(self, nums):
        mask = 0
        for n in nums:
            mask ^= n

        mask &= (-mask) 

        a, b = 0, 0
        for n in nums:
            if n & mask:
                a ^= n
            else:
                b ^= n
        return [a, b]

371. Sum of Two Integers

用^和&，构成加法运算

^表示相加后的结果，&后的<< 1表示相加后的进位 (理解加减法的位操作)

// Java - Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

// Java - Recursive
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

1 异或

异或^