数组中唯一只出现一次的数字

题目：

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

分析：

1. 如果题目是：数组中除一个数字出现一次之外，其他数字都出现了两次。我们可以使用 XOR 异或位运算解决这个简化的问题。由于两个相同的数字异或结果是 0，我们把数组中所有的数字异或的结果就是那个唯一只出现一次的数字。
2. 但这种思路不能结局当前的问题，因为三个相同的数字异或结果还是该数字。这里不能使用异或运算，但还是可以使用位运算的思路。如果一个数字出现三次，那么它的二进制表示的每一位（0或者1）也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被3整除。
3. 我们把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除，那么那个只出现一次的数字二进制表示中对应的那一位是0；否则是1。

代码：

class OnceAppearSolution {

    public static int findNumberAppearOnce(int[] data, int length) {
        if (null == data || length <= 0) {
            throw new RuntimeException("params error");
        }

        int[] bitSum = new int[32];
        for (int i = 0; i < length; i++) {
            int bitMask = 1;
            for (int j = 31; j > 0; j--) {
                // 依次判断数字上每一位是否为1
                int bit = data[i] & bitMask;
                if (bit != 0) {
                    bitSum[j] += 1;
                }
                bitMask = bitMask << 1;
            }
        }

        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = result << 1;
            result += bitSum[i] % 3;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 1, 2, 3, 1, 2};
        System.out.println(findNumberAppearOnce(data, data.length));
    }
}

总结：

1. 判断某个数x的第n位（如第3位）上是否为1，

1）通过 x&00000100 的结果是否为0 来判断。（不能根据是否等于1来判断）

2）通过（x>>3)&1 是否为0 来判断

2. 通过number&bitMask的结果是否为0（不能用1判断），bitMask=1不断左移，可以将一个数的二进制存储到32位的数组中。

`int` `number=``100``;``int` `bitMask=``1``;``for``(``int` `j=``31``;j>=``0``;j--) {``    ``int` `bit=number&bitMask;  ``//注意arr[i]&bitMask不一定等于1或者0，有可能等于00010000``    ``if``(bit!=``0``)``        ``bits[j]=``1``;``    ``bitMask=bitMask<<``1``;``}`

3. 通过以下代码实现二进制转化为数字（注意左移语句的位置）：

`int` `result=``0``;``for``(``int` `i=``0``;i<``32``;i++) {``    ``result=result<<``1``;``    ``result+=bits[i];``    ``//result=result<<1;  //不能放在后面，否则最前面一位就没了``}`

参考：

https://www.cnblogs.com/yongh/p/9960447.html