XOR异或解惑

https://leetcode.com/problems/single-number-ii/

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

在网上看了解答，其中一种解法是用二进制模拟三进制，代码如下：

 1 int singleNumber(int A[], int n) {
 2     int ones = 0, twos = 0, xthrees = 0;
 3     for(int i = 0; i < n; ++i) {
 4         twos |= (ones & A[i]);
 5         ones ^= A[i];
 6         xthrees = ~(ones & twos);
 7         ones &= xthrees;
 8         twos &= xthrees;
 9     }
10     return ones;
11 }

 1 class Solution {
 2 public:
 3     int singleNumber(int A[], int n) {
 4         int one,two,three;
 5         one=two=three=0;
 6         for(int i=0;i<n;i++)
 7         {//一定是出现3次，2次，1次这样的顺序，如果反过来的话，先更新了one的话，会影响到two和three的
 8             three =  two & A[i];//已经出现了两次，还出现了一次
 9             two = two | one & A[i];//出现了1次又出现了1次，在加上以前已经出现了2次的，为新的出现了2次的
10             one = one | A[i];//出现了1次
11             //将出现3次的其出现1次2次全部抹去
12             one = one & ~three;
13             two = two & ~three;
14         }
15          return one;
16     }
17 };

这个是用ones 和 twos 分别表示两个bit，要实现计算3的倍数，这俩bit的变化规律是 (注意实际运算中A[ i ]就相当于1)

twos    ones
  0       0
  0       1
  1       0
  1       1
  0       0
当ones和twos都达到1时，用xthrees把他们都重置为0，这就是xthrees开始那三行的作用
那么前两行计数  他利用的规律是
第一行计算twos ：当ones是0时，twos不变，（利用了 x|0==x）当ones是1，twos变为1 ( ones 是1 twos 一定是0 而 0|x==x）
第二行计算ones ：简单的xor，偶数次为0，奇数次为1

顺便贴个讨论里那个更简洁的代码原理一样的

1 public int singleNumber(int[] A) {
2         int zeros=0, ones=0;
3         for (int i=0; i<A.length; i++){  // 00 -> 01 -> 10 -> 00
4             zeros = (zeros^A[i]) & ~ones;  // if bit1 is 1 we should put bit0 as 0, otherwise just count
5             ones = (ones^A[i]) & ~zeros;  // if bit0 is 1 we should put bit1 as 0, otherwise just count
6         }
7         return zeros|ones;
8 }

其实只要理解什么是XOR就好。

A XOR B = (A+B)%进制。
如果是10进制，7 XOR 8 = (7+8)%10 = 5
一种思想就是把二进制XOR改成三进制XOR就好

所谓single number，其实就是bit统计
你可以按照 bit by bit 统计
single number II，你可以把bit加到一起
所有number第一bit的sum
所有number第二bit的sum...
然后sum%3 (bit by bit) 就是结果...

single number问题最难的是k number问题
Given an array of integers, every element appears X times except for k numbers (that only appear once). Find that k numbers.

其实就是有点不能理解为什么A XOR B = (A+B)%进制？“A XOR B”就是一个确定的数，后面的“进制”是可变的，这两个东西怎么能相等？
你下面说的这个方法我倒是能理解，当时提交的时候也是用这个方法过的，我只是看到另外那种解法对位运算这些东西有点看不懂所以贴出代码问问大家。

7+8 = 15 是十进制+定义

7+8 = F 是十六进制+定义

A XOR B = (A+B)%进制这就是XOR的一种定义，结果就是和进制本身有关重复相加到进位，然后不进位而归零，叫做XOR，如果进位，就叫做加法

// K number
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int len = sizeof(int) * 8;
        int res = 0;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = 0; j < nums.size(); j++) {
                sum += (nums[j] >> i) & 0x01;
            }
            res += (sum % 3) << i;
        }
        return res;
    }
};

时间：O(32*N)，这是一个通用的解法，如果把出现3次改为 k 次，那么只需模k就行了。

http://www.1point3acres.com/bbs/thread-111563-1-1.html

XOR异或解惑

推荐阅读