leetcode single-number-ii

n个数，只有一个数出现1次 其他每个数都出现了3次 找出只出现一次的数。

显然先想到的就是按位加模3了，拿一个数组去记数的二进制每一位，大概long long的数复杂度O(64*n)。常数略大，进而想到用位运算来优化，拿两个变量，one和two分别记录到当前为止，哪些位只出现了单独1个1，哪些位恰出现了2个1，每次循环处理到当前的数，先去和two看能不能凑够3个1就可以把two的当前位消为0，然后当前数消剩下的去和one比对看能不能凑够2个1就可以将two相应位置1，最后把消剩下的数全部给one即可。最后答案就是one

int singleNumber(int a[], int len){ 
     int one = 0;
     int two = 0;
     int remain;
     for(int i = 0; i < len; ++i){
            remain = a[i] & ~two;
            two &= ~a[i];
            two |= one & remain;
            one ^=remain;
     }
     return one; 
} 

leetcode single-number-ii,布布扣,bubuko.com

leetcode single-number-ii

原文：http://blog.csdn.net/waitfor_/article/details/21163985