Single Number II （LeetCode Bit Manipulation)

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

Idea: If we think the numbers as binary numbers. At the i'th bit, if a number shows up 3 times, the sum of the i'th bit 3 times %3==0, however, the number shows up 1 times, the sum of the i'th bit %3==original bit value.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int singleNumber(int[] A) {  
     int ones=0,twos=0,threes=0;  
     for(int i=0;i<A.length;i++)  
     {  
       twos|=ones&A[i];  
       ones^=A[i];  
       threes=ones&twos;  
       ones&=~threes;  
       twos&=~threes;  
     }  
     return ones;  
   }  
 }