面试题4：只出现一次的数字（Java版）

题目：输入一个整数数组，数组中只有一个数字出现了一次，而其他数字都出现了3次。请找出那个只出现一次的数字。例如，如果输入的数组为[0，1，0，1，0，1，100]，则只出现一次的数字是100。

// 因为只有一个数出现了一次，其余的数都是出现了3次
// 所以出现了三次的数它们的每个二进制位相加一定能够被三整除
// 如果哪一个数位不能被三整除，则证明那个出现1次的数在该数位的值为1
// 如果能被整除，则证明出现一次的那个那个数该数位为0
public static int singleNumber(int[] nums) {
    int[] bitSums = new int[32];
    for (int num : nums) {
        for (int i = 0; i < 32; i++) {
            // 右移31 - i位相当于把该数第i数位移到了最右边与1求与则正好把最
            // 右边那个数单独取出来，然后把该数位的值加到bitSums数组对应数位位置上
            bitSums[i] += (num >> (31 - i)) & 1;
        }
    }

    int result = 0;
    for (int i = 0; i < 32; i++) {
        // 左移一位加上对应数位求余的值相当于把每个数位上的数加到对应数位上
        result = (result << 1) + bitSums[i] % 3;
    }
    return result;
}