剑指56：数组中只出现一次的数字——异或——位运算

题目描述1：数组中只出现一次的数字

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

思路： 一个整型数组只有一个数字出现一次 其他出现2次 考虑异或全部得到唯一的这个数字。
            同理，将问题分组成2组，每组保证有一个出现1次的数，且每组中其他数都出现2次。
            考虑通过数某一位是否为1的特征进行分组。

class Solution {
public:
    bool FindBit1(int num,int pos){
        num=num>>pos;
        return (num&1);
        
    }
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.empty())
            return;
        //数组内异或 获得异或结果seed 其二进制表示一定含有不只1个1
        int seed = 0;
        for(int i=0;i<data.size();i++){
            seed ^= data[i]; 
        }
        //找到seed二进制中1的位置（从右到左移动次数）
        int FindIndexOf1 = 0;
        while(FindIndexOf1<8*sizeof(int)&&((seed&1)==0)){
            seed = seed>>1;
            FindIndexOf1++; //记录移动次数
        }
        //分成两组，分别异或
        *num1=0,*num2=0;
        for(int i=0;i<data.size();i++)
        {
            if(FindBit1(data[i],FindIndexOf1))
                *num1 ^= data[i];
            else
                *num2 ^= data[i];
        }
    }
};

题目描述2：数组中唯一只出现一次的数字

题目：在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请 找出那个吃出现一次的数字。

思路：出现3次的多个数和唯一出现1次的数 他们的二进制位对应相加的数被3整除 则目标数该位是0否则是1

// 面试题56（二）：数组中唯一只出现一次的数字
// 题目：在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请
// 找出那个吃出现一次的数字。

#include <cstdio>
#include <exception>
#include<stdexcept>
#include<iostream>
#include<string.h>

//思路：出现3次的多个数和唯一出现1次的数 他们的二进制位对应相加的数被3整除 则目标数该位是0否则是1
int FindNumberAppearingOnce(int numbers[], int length)
{
    std::logic_error error("Invalid");
    if(!numbers||length<=0)
        throw std::exception(error);
    int bitSum[32]={0};
    //遍历整型数组 对二进制的每一位进行计算 累计数组中每个数在32位二进制中当前位的和
    for(int i=0;i<length;i++){
        int bitMask = 1;
        //32位二进制 每一位求值累加
        for(int j =31;j>=0;j--){
            int bit = numbers[i]&bitMask;
            if(bit!=0)
                bitSum[j] += 1; //bit可能是大于0的任何数
            bitMask = bitMask<<1;
        }
    }
    //计算32位数组中每一位是否能被3整除
    int result = 0;
    for(int j=0;j<32;j++){
        result = result<<1;  //在遇到第一个被3整除的非零数时先移位一次 保证有效移位数比总位数少1
        result += bitSum[j]%3;
    }
    return result;
}