Single Number II

https://leetcode.com/problems/single-number-ii/
给定一个整数数组，长度为3n+1，其中有n个数字都出现了3次，只有一个数字出现了一次，找出这个数字
Input: [2,2,3,2]
Output: 3

解析

是不是首先想到了位运算，是不是发现跟2n+1的逻辑不一样？ 2n+1的题目直接异或出来的结果就是最终不同的值，而这个不是，这个能异或吗？ 不能~

我们还是考虑用二进制的位运算
怎么用，talk is cheap， show me your example
先看一个简单的例子：

[2,2,3,2]
2+2+2 = 6 是可以被3 整除的
对应的二进制
 10
+10
+10
---------
=30
诶，二进制对应的每一位3也是可以被3整除的
当我们再加上3之后会变成
 30
+11
———————————————
=41
显然被3整除不了了

就是利用的上面这个特性，怎么利用呢？

来，再看一个复杂点的例子：

假定我们的array of integers为[1,2,2,1,1,2,4,4,5,4]，写成二进制位就是：
1：0001
2：0010
2：0010
1：0001
1：0001
2：0010
4：0100
4：0100
5：0101
4：0100
T：0434 (这个T代表所有的数字的每一位加起来之后的结果)
R：0101(这个R代表T中的每一位进行模3之后的结果)
很巧妙的是  这个R就是5的二进制，二我们的结果就是5

OK，下面就是我们结果的代码

//java
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 64; i++) {
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                sum += (nums[j] >> i) & 1;//这里为什么要&1？  因为我们要的是右移i位后对应的二进制是0或者1，可以试试10右移1位之后对应的数字是多少，而&1 之后对应的数字是多少？
            }

            res |= (sum % 3) << i;
        }
        return res;
    }