思路：

  • 相同为0，不同为1
  • 遇到数组中求出现奇数次的数字，其余为偶数次

例如：

剑指 Offer II 070. 排序数组中只出现一次的数字

此题为：出现奇数次的个数只有一个的数字，其他为偶数次；所以一遍异或就可以得到偶数次异或都为0，最终为：0^a = a； 
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for(int i : nums){
            res ^= i;
        }
        return res;
    }
}


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

  • 此题为：出现奇数次的个数有两个的数字，其他为偶数次；所以一遍异或只能得到 res = a ^ b；
  • 还需要分组，进一步遍历；将a、b分别放在不同的两块，所以按照条件遍历就可以得到temp = a或者b；
  • 所以b或者a，就可以用res ^ temp 
class Solution {
    public int[] singleNumbers(int[] nums) {
        int[] res = new int[2];
        // 此时的sum就是这两个数异或
        int sum = 0;
        for(int i : nums){
            sum ^= i;
        }

        // 找到最右侧的位置为1，也就是将两个数分别放值在两侧
        int flag = sum & (~sum + 1);

        for(int i : nums){
            if((flag & i) == 0){
                // 得到两个数其中的一个数
                res[0] ^= i;
            }
        }

        res[1] = res[0] ^ sum;

        return res;
    }
}

461. 汉明距离 

class Solution {
    public int hammingDistance(int x, int y) {
        // 异或得出不同位置
        int nums = x ^ y, count = 0;
        
        while(nums != 0) {
            // 求出每一位是否为1
            count += nums & 1;
            nums = nums >> 1;
        }

        return count;
    }
}


338. 比特位计数 

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            res[i] = getCount(i);
        }

        return res;
    }

    public int getCount(int i) {
        int count = 0;
        while(i != 0) {
            count += i & 1;
            i = i >> 1;
        }

        return count;
    }
}