# Comparing three solutions

• Solution 1:

Suppose the required return value is ret. Each bit of ret is calculated by the respective bit of A[0:n-1].

int singleNumber3(int A[], int n) {
int m=32;
int ret = 0;
while(m--)
{
ret = ret >> 1;
ret &= 0x7fffffff;
int sum = 0;
for(int i=0;i<n;i++)
{
sum += A[i] & 0x00000001;
A[i] = A[i] >> 1;
}
if(sum%3){
ret |= 0x80000000;
}
}
return ret;
}

Solution2:
Solution1 needs 32*n passes of loop. Solution2 is found on the Internet, see http://blog.csdn.net/bigapplestar/article/details/12275381 . However the bit operation is confused. Therefore I write solution3, and try to explain it.

public int singleNumber(int[] A) {
int once = 0;
int twice = 0;
for (int i = 0; i < A.length; i++) {
twice |= once & A[i];
once ^= A[i];
int not_three = ~(once & twice);
once = not_three & once;
twice = not_three & twice;
}
return once;
}

Solution3:

My solution3 seems more easy-to-understand compared with solution2. Suppose the i-th bit of one, two, thr (one_i, two_i, thr_i) is used to count how many bits in A[0-n-1]_i is 1.
# one_i two_i thr_i
1 1 0 0
2 0 1 0
3 0 0 0
4 1 0 0
5 0 1 0
6 0 0 0
....

so we have:

if(A[i] == 1)
if(one == 0)
one = 1;
else
one = 0;
if(two == 0)
two = 1;
else
two = 0;
if(thr == 0)
thr = 1;
else
thr = 0;
when thr=1
one=two=0;

So with the bit operation we have:

int singleNumber3(int A[], int n) {
int one=0, two=0, thr=0;
while(n--)
{
//thr ^= (one & two & A[n] );
two ^= one & A[n];
one ^= A[n];
thr = one & two;
one = (~thr) & one;
two = (~thr) & two;
//thr = (~thr) & thr;
}

Hope this may help.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.