137. Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Statement of our problem: "Given an array of integers, every element appears k (k >1) times except for one, which appears p times(p>=1, p % k != 0). Find that single one." 这类问题的通解

public class Solution {
    public int singleNumber(int[] nums) {
        int x1 = 0;
        int x2 = 0;
        int mask = 0;
        for(int num : nums) {
            x2 ^= (x1 & num);
            x1 ^= num;
            // k = 3, k1 = 1, k2 = 1 
            mask = ~(x1 & x2);
            x1 &= mask;
            x2 &= mask;
        }
        // p = 1, binary form p = '01', return x1
        return x1;
    }
}