Single Number II Solutions in C++

// Source : https://oj.leetcode.com/problems/single-number-ii/
// Author : Hao Chen
// Date   : 2014-06-17



class Solution {
public:
    Solution(){
        srand(time(0));
    }
    
    //random invoker
    int singleNumber(int A[], int n) {
        if (rand()%2){
            return singleNumber_1(A, n);
        }
        return singleNumber_2(A, n);
    }

    /*
     *  This solution is clear & straightforward implementation.
     *  
     *  We use an array of 32 length(e.g. count[32]) to count the the bits for all of numbers. 
     *
     *  Because the same number appear 3 times, which means the sum of i-th bits for all numbers should be 3 times.
     *
     *  In other word, the sum of the i-th bits mod 3, it must be 0 or 1. 1 means that is the single number bit.
     *
     * This solution can be easy to extend to "every element appears k times except for one."
     *
     */
    int singleNumber_1(int A[], int n) {
        int count[32] = {0};
        int result = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++) {
                if ((A[j] >> i) & 1) {
                    count[i]++;
                }
            }
            result |= ((count[i] % 3) << i);
        }
        return result;
    }


    /*
     *   The following solution is popular solution on Internet, but it looks it's not easy to understand.
     *
     *   Actually, it just optimizes the above soultion.
     *
     *   Let's see how it improve the above.
     *
     *   We use three bitmasks, 
     *    1) `ones`     as a bitmask which represents the i-th bit had appeared once.
     *    2) `twos`     as a bitmask which represents the i-th bit had appeared twice.
     *    3) `threes`   as a bit mask which represents the i-th bit had appeared three times.
     *
     *    When the i-th bit had appeared for the third time, clear the i-th bit of both `ones` and `twos` to 0.
     *    The final answer will be the value of `ones`
     *
     */
    int singleNumber_2(int A[], int n) {
        int ones = 0, twos = 0, threes = 0;
        for (int i = 0; i < n; i++) {
            // `ones & A[i]` the result is the bitmask which the bits appeared twice
            twos |= ones & A[i]; 
            // XOR means remove the bit which appeared twice int `ones` 
            ones ^= A[i];
            // count the `three`
            threes = ones & twos;
            // clear the `ones` and `twos` if the i-th bit had appeared three times.
            ones &= ~threes;
            twos &= ~threes;
        }
        return ones;
    }

};

class Solution {
    public:
        int singleNumber(int A[], int n) {
            int low = 0;
            for (int i = 0, high = 0; i != n; ++i)
            {
                low ^= A[i] & ~high;
                high ^= A[i] & ~low;
            }
            return low;
        }
};