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

题目描述：

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

int[] counts = new int[32];
for(int i = 0; i < nums.length; i++) {
    for(int j = 0; j < 32; j++) {
        counts[j] += nums[i] & 1; // 更新第 j 位
        nums[i] >>>= 1; // 第 j 位 --> 第 j + 1 位
    }
}

将 countscounts 各元素对 3 求余，则结果为 “只出现一次的数字” 的各二进制位。

for(int i = 0; i < 32; i++) {
    counts[i] %= 3; // 得到 只出现一次的数字 的第 (31 - i) 位 
}

利用 左移操作 和 或运算 ，可将 counts 数组中各二进位的值恢复到数字 res 上（循环区间是 i∈[0,31] ）。

for(int i = 0; i < counts.length; i++) {
    res <<= 1; // 左移 1 位
    res |= counts[31 - i]; // 恢复第 i 位的值到 res
}

 实际上，只需要修改求余数值 m ，即可实现解决 除了一个数字以外，其余数字都出现 m 次 的通用问题。

class Solution{
    public int singleNumber(int nums[]){
        int count[] = new int[32];
        for(int num:nums){
            for (int j=0;j<32;j++){
                count[j]+=num&1;
                num>>>=1;
            }
        }
        int res=0,m=3;
        for(int i=0;i<32;i++){
            res<<=1;
            res|=count[31-i]%m;
        }
        return res;
    }
}

注：

1、&(按位与)运算操作符，在计算机底层计算的原理中，相同位置的二进制序列进行对比，只要有0就是0，两个都是1才是1。

2、|(按位或)运算操作符，在计算机底层计算的原理中，相同位置的二进制序列进行对比，只要有1就是1，两个都是0才是0。

3、^(按位异或)运算操作符，在计算机底层计算的原理中，相同位置的二进制序列进行对比，相同为0，相异为1。

4.^=：两个二进制的对应位相同，结果为0，否则结果为1。a^=b 等效于 a=a^b 按位异或并赋值。