XOR

规则

0 ^ 0 = 1 ^ 1 = 0

1 ^ 0 = 0 ^ 1 = 1

a ^ a = 0

Single Number

找数组里只有出现一次的那个数，别的数都出现两次

public class Solution {
    public int singleNumber(int[] nums) {
        int n = 0;
        for (int num: nums) {
            n ^= num;
        }
        return n;
    }
}

Find the Difference

找唯一insert的那个character

public class Solution {
    public char findTheDifference(String s, String t) {
        char c = 0;
        for (int i = 0; i < s.length(); i++) {
            c ^= s.charAt(i);
            c ^= t.charAt(i);
        }
        c ^= t.charAt(t.length() - 1);
        return c;
    }
}

Missing Number

找唯一missing的那个数字，拿数值和index做xor

public class Solution {
    public int missingNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= i;
            result ^= nums[i];
        }
        result ^= nums.length;
        return result;
    }
}

Single Number III

有两个唯一出现一次的数字，剩下的其他数字都出现两次。

按Single Number I里方法做xor以后，我们得到的结果实际就是那两个single number做了xor后的结果。

那这个数的各个digit上，数字为1的digit可以被用来区分这两个数。

int lastOneBit = xor & -xor。这个lastOneBit来到的结果就是从最低位看过来第一个出现了1的那个数值。拿这个lastOneBit对整个数组分类既可以得到我们想要的两个数。

public class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num: nums) {
            xor ^= num;
        }

        int lastOneBit = xor & -xor;
        int num1 = 0, num2 = 0;
        for (int num: nums) {
            if ((num & lastOneBit) == 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }

        return new int[]{num1, num2};
    }
}