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

问题：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路：136. 只出现一次的数字 即如果除了一个数字以外，其他数字都出现了两次，我们可以用异或求解出这个数字。这是求解一个出现一次的数字，而这道题有两个出现一次的数字需要求解。我们考虑将数组分为两组，且这两个出现一次的数字分别在一组，然后再使用异或的方法就可以求出这两个数字。具体如下：

假设这两个数字分别为a，b。将数组中所有元素异或后，得到的结果res为a ^ b。此时考虑res的二进制位的意义，某一位为0，说明a和b这一位同为0或同为1。某一位为1，则表示a与b这一位不相等，即一个这一位为0，另一个这一位为1。根据这个不同位，也就是res某一位为1，将数组分组，肯定可以将a和b分开分到两组。res可能会有许多位为1的情况，我们只需要取某一位就行。可以选择最低位1的位置，假设是第i位。然后根据第i位将数组分组，对于数组中的每个元素来说，若第i位为1，分为一组，否则分为另一组，分组的同时分别对两组元素进行异或运算，最后得到的两个结果即为所求。

求解res最低位1的位置，

• 官方题解给的方法是：令firstOne=1，然后与上res即res & firstOne。若为0，则firstOne左移一位，继续判断，直到找到为止。这里需要注意的是firstOne是一个只有一位为1的数，所以res & firstOne的结果有两种：0或firstOne。则while循环的判断条件不能是(res & firstOne) != 1。我第一次就是这样写的，结果发现有个示例超时了。
• 还有一种评论里的求法，很巧妙：firstOne = res & (-res)。以18为例，-18的二进制表示就是18二进制表示的补码，也就是反码加1。18的二进制表示为1010。它的反码为0101，再加1为0110。则18 & (-18)即1010 & 0110 = 0010。这样可以快速求得18最低位1的位置。

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

        int firstOne = res & (-res);
        // while((res & firstOne) == 0){
        //     lastOne <<= 1;
        // }

        int a = 0, b = 0;
        for(int num: nums){
            if((firstOne & num) == 0){
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

整理思路，记录博客，以便复习。若有误，望指正~