数组中只出现一次的数（其它数出现k次）

题目：

给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。 已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。 请返回只出现了 1 次的数。

示例：

输入：[5,4,1,1,5,1,5],3

返回值：4

输入：[2,2,1],2

返回值：1

解题思路：

使用位操作的异或来解决

假设数组中没有只出现一次的数，那么数组中所有的数字都出现了k次，比如示例中的[1, 5, 1, 5, 1, 5]用二进制表示为

1：0001；

5：0101；

1：0001；

5：0101；

1：0001；

5：0101

—————

0 3 0 6

每位上1的个数均能被3整除。

此时对该数组添加任何一个数，如果这个数在二进制的某位上为1都将导致该位上1的个数不能被3整除。因此通过统计二进制上每位1的个数就可以推断出该数在相应位置上是0还是1了，从而计算出该数。

代码示例：

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param arr int一维数组 
 * @param arrLen int arr数组长度
 * @param k int 
 * @return int
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int foundOnceNumber(int* arr, int arrLen, int k ) {
    // write code here
        int bits[32];
        int i, j;
  // 累加数组中所有数字的二进制位
        memset(bits, 0, 32 * sizeof(int));
        for (i = 0; i < arrLen; i++)
            for (j = 0; j < 32; j++)
                bits[j] += ((arr[i] >> j) & 1);
  // 如果某位上的结果不能被整除，则肯定目标数字在这一位上为
        int result = 0;
        for (j = 0; j < 32; j++)
            if (bits[j] % k != 0)
                result += (1 << j);
        return result;

}