Contents

1. 1. 题目：
2. 2. 分析：

参考：http://blog.csdn.net/morewindows/article/details/12684497

题目：

数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法找到x。

分析：

如果数组中没有x，那么数组中所有的数字都出现了3次，在二进制上，每位上1的个数肯定也能被3整除。如{1, 5, 1, 5, 1, 5}从二进制上看有：
1：0001
5：0101
1：0001
5：0101
1：0001
5：0101
二进制第0位上有6个1，第2位上有3个1.第1位和第3位上都是0个1，每一位上的统计结果都可以被3整除。而再对该数组添加任何一个数，如果这个数在二进制的某位上为1都将导致该位上1的个数不能被3整除。因此通过统计二进制上每位1的个数就可以推断出x在该位置上是0还是1了，这样就能计算出x了。

• 可试用于正数，负数，0

推广一下，所有其他数字出现N（N>=2）次，而一个数字出现1次都可以用这种解法来推导出这个出现1次的数字。

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

int findNumber(int arr[], int n){

    int bits[32];
    memset(bits, 0, sizeof(bits));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 32; j++){
            bits[j] += ((arr[i] >> j) & 1);
        }
    }
    int result = 0;
    for(int i = 0; i < 32; i++){
        if(bits[i] % 3 != 0){
            result += (1 << i);
        }
    }
    return result;
}

int main(){

    //int a[4] = {0, 0, 0, 1};
    //int a[4] = {1, 1, 1, 0};
    //int a[10] = {-1, -1, -1, -4, -3, -3, -3, 7, 7, 7};
    //int a[10] = {-1, -1, -1, 2, -3, -3, -3, 7, 7, 7};
    int a[10] = {2, 3, 1, 2, 3, 4, 1, 2, 3, 1};
    printf("%d\n", findNumber(a, 10));
    return 0;
}