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?
Solution:
看到大神的解法： http://www.mitbbs.com/article_t/JobHunting/32547143.html
整数的32个bits，出现次数mod 3后必余0, 1, 2，其中余1的就是答案
public int singleNumber(int[] A) { int n1=0,n2=0; for(int i=0;i<A.length;++i){ int n0=~(n1|n2); // 若非余1也非余2，就是余0了 n2=(n1&A[i])|(n2&~A[i]); // 若「原本就余2且bit为0」或「原本余1且bit为1」，则该bit更新后余2 n1=(n1&~A[i])|(n0&A[i]); // 若「原本就余1且bit为0」或「原本余0且bit为1」，则该bit更新后余1 } return n1; }
原文：http://www.cnblogs.com/Phoebe815/p/4053362.html