[leetcode][****] 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?

Algorithm:

This problem is very hard actually. The train of thought is that, %3. 

1) For every bit of each number, we should make the count of 1 mode 3. If repeated n times, then mode n.

2) As the result of %3 can be 0,1,2. Then the result should be kept in two bits instead of one. 

3) should think about for all one bit numbers as {a1, a2, ...., a3}. how to calculate 

    (a1 + a2 + a3+ ...+ an)%3 with bit operation. (&, |, ^). This is also hard to see. Then check the easier 

    problem of (a+b)%3. The truth table shoule be:

    a    b     results

    0   0      0    0

    0   1      0    1

    1   0      0    1

    1   1      1    0