Single Number II——系列标题的翻译

题目：
Given an array of integers, every element appears three times except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


https://oj.leetcode.com/discuss/6632/challenge-me-thx

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

一眼看来代码有点复杂难以理解，然而，若用boolean代数的形式考虑问题，一切那么自然。

我们需要做的就是存储每一位出现1的次数（由于32位的每一位都是有通用的计算规则，就只需考虑一个bit，我们直到一个数字最多出现3次，因此我们仅需2bits来存储每一个位上的变化，现在我们就有4个状态00,01,10和11,但仅需用到其中三个）

这个解决方法选择了00,01,和10三个状态，使'ones'代表第一个bit，'twos'代表第二个bit。然后我们需要制定一些规则使得'ones'和'twos'执行我们所想，目标的环路是00->01->10->00(0->1->2->3/0)

• 对'ones'来说，得到'ones = ones^A[i];如果twos==1那么ones = 0',可以用'ones = (one^A[i])& ~twos'来表示
  
• 同样，对于'twos'来说，得到'twos = twos^A[i];如果ones* == 1那么twos = 0' 和'twos = (twos^A[i])&~ones'.注意'ones*是'ones'计算后的值，这也是为何twos后计算。
  

---

这有另外一个例子，如果一个数字最多出现5次，我们可以用类似方法写出程序，现在我们需要3bits，环路未000->100->010->110->001。代码如下所示。

int singleNumber(int A[], int n) {
    int na = 0, nb = 0, nc = 0;
    for(int i = 0; i < n; i++){
        nb = nb ^ (A[i] & na);
        na = (na ^ A[i]) & ~nc;
        nc = nc ^ (A[i] & ~na & ~nb);
    }
    return na & ~nb & ~nc;
}

也可以跟这里一样：

int singleNumber(int A[], int n) {
    int twos =～0, threes = ～0, ones = 0;
    for(int i = 0; i < n; i++){
        threes = threes ^ (A[i] & twos);
        twos = (twos ^ A[i]) & ~ones;
        ones = ones ^ (A[i] & ~twos & ~threes);
    }
    return ones;
}