题目：
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?代码：
class Solution {public: int singleNumber(vector & nums) { int result = 0; const int W = sizeof(int)*8; int *count = new int[W](); for (size_t i = 0; i < nums.size(); ++i) { for (size_t j = 0; j < W; ++j) { count[j] += (nums[i] >> j) & 1; } } for (size_t i = 0; i < W; ++i) { if ( count[i]%3!=0 ) { result += ( 1 << i); } } delete []count; return result; }};
Tips:
1. 算法原理：由于都是int型的，只需要记录每个bit上1出现的次数；如果1出现的次数不是3的倍数，则将该位置置为1，并赋值到result中。
这道题主要是熟悉下位运算的各种操作，有时巧用位运算，可以大大提升代码效率。
================================================================
学习了另一种解法，代码如下：
class Solution {public: int singleNumber(vector & nums) { int one=0, two=0, three=0; for (size_t i = 0; i < nums.size(); ++i) { two |= (one & nums[i]); one ^= nums[i]; three = two & one; one &= ~three; two &= ~three; } return one; }}; 参考链接：
简单说就是，用二进制模拟三进制运算。
循环体中的五条语句分别做了如下的事情：
1. 算上nums[i]之后，1出现了两次的bit位数有哪些
（包括两种情况：a.原来就是2次的，nums[i]在该bit上是0；原来是1次的，nums[i]在该bit上是1）。
2. 算上nums[i]之后，1出现了一次的bit位数有哪些。
3. 算上nums[i]之后，1出现了三次的bit位数有哪些
4和5. 满3进位，清空。
这里可能会有一个疑问：1出现次数为一和为二的能否算重了？
假设nums[i]在某一个bit上是0：
a. 算two的时候，这一位不会影响原来two这一bit的取值。
b. 算one的时候，相当于该bit与0异或，保持不变。
假设nums[i]在某一个bit上是1：
a. 算two的时候，如果one在该bit上也是1，则two这一bit取1，如果one在这一位上是0，则two这一bit上不变。
b. 算one的时候，相当于该bit与1异或，取反。如果one原来是1，则进位，one置为0；如果one原来是0，则变为1。
对比颜色相同的两端文字，可以知道是不会算重复的。
想到这里还有一个疑问：two = two | (one & nums[i])，如果某一bit上two原来就是1，并且还有进位了，那这？
这种case是不可能出现的：因为one two three初始都是0，假如连着三个nums[i]在某个bit上都为1，则three在该bit上就为1了。后面两条语句，就保证了two和one被清空了，因此永远不会出现two原来是1并且有进位的情况。
======================================================
第二次过这道题，想了一段时间。大体思路已经想出来了，但是位运算操作（“左移多少位再跟1进行与操作”这些的技巧）参考了书上的code。代码还是一次AC了。
class Solution {public: int singleNumber(vector & nums) { int int_bits = sizeof(int)*8; vector count(int_bits,0); // count each '1' in each bit for ( int i=0; i > j) & 1; count[j] = count[j] % 3; } } // extract single number int single = 0; for ( int i=0; i 还是这种思路好记一些，二进制代替三进制运算的那个并没有印象了。