05 August 2008
把每一位数都想成二进制的数，用一个32位的数组来记录每一位上面的1的count值。注意数组计数是从左往右走，而二进制数数是从右往左的；所以数组第0位的count就是二进制最低位上的count的。例如：4的二进制是100（当然作为32位就是前面还一堆了000…000100这样子），3个4的话按照每位相加的话，按照二进制表示法考虑就是300，当然存在数组里面就是003（A[0]=0;A[1]=0;A[2]=3，然后后面到A[31]都得0）。
然后对所有数按照二进制表示按位加好后，就要把他还原成所求的值。这里面的想法是，如果一个数字出现了3次，那么这个数字的每一位上面，如果有1那么累加肯定是得3的，如果是0，自然还是0。所以对每一位取余数，得的余数再拼接起来就是我们要找的那个single one。
这里还原的方法是，对32位数组从0开始，对3取余数，因为数组0位置其实是二进制的最低位，所以每次要向左移。用OR（|）和 + 都可以拼接回来。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int i = 0; i < 32; i++) {
int sum = 0; //位操作一个整数就是32位
for (int num : nums) {
sum += (num >> i) & 1; //通过右移计算该位上，所有数组中数字的1的个数
}
result |= (sum % 3) << i; // 除以3相当于“去掉三个重复数”，然后再左移还原i位，然后|拼接还原
}
return result;
}
}