从零学算法（LCR 178）

n  one newone
0  0   0
0  1   1
1  0   1
1  1   0
1
2
3
4
5

• 可以看到符合异或运算，即

•   if two==0:
    	one = one^n
    if two==1:
    	one = 0 
  1
  2
  3
  4

• 接着简化，老样子，真值表，这里把 one^n 暂时记作 one

two one newone
0   one  one   
0   one  one
1   one  0
1   one  0
1
2
3
4
5

• 这个就稍复杂一点点，x?0=x, x?1=0，我们知道 x&1=x, x&0=0，但是这里正好相反，是 0 和 1，因为 ~0=1，~1=0 ，那么不难想到了， x&~0=x, x&~1=0，所以我们就得到了 newone = one &~two，把 one^n 再代入回来，我们最终得到了
• one = (one^n) & ~two
• 我们还得根据计算出的 one 继续计算出 two，按道理我们是需要根据旧的 one 来加 n 计算出 two，那我们还是一样先真值表，根据旧的 two 和 n 以及 新的 one，推算出旧的 one，然后得到新的 two
  
• two old：当前 two 的值
• 第一行：two 为 0，n 为 1，新的 one 为 1，说明之前的 two，one 为 00，（two，one 我就简称为 x 吧），所以 00+1 = 01，新的 two 为 0；
• 第二行：two 为 0，n 为 1，新的 one 为 0，说明之前的 x 为 01，01+1=10，新 two 为 1
• 第三行：two 为 1，n 为 1，新 one 为 0，说明之前的 x 为 10，其实 two 为 1，x 只可能是 10，10+1=00，新 two 为 0
• 不用我继续写了吧，根据真值表我们先得到最朴素的 6 个 if

•   if two==0:
    	if n==0:
    		if one == 0:
    			two = two
    		elif one == 1:
    			two = two
    	if n==1:
    		if one == 0:
    			two = 1 #~two
    		if one == 1:
    			two = two
    elif two==1:
    	if n==0:
    		if one == 0:
    			two = two
    	if n==1:
    		if one == 0:
    			two = 0 #~two
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

• 简化一下，结果还是为 two 的情况可以省略：

•   if two==0:
    	if n==1:
    		if one == 0:
    			two = 1
    elif two==1:
    	if n==1:
    		two = 0
  1
  2
  3
  4
  5
  6
  7

• 继续简化：

•   if two==0:
    	if n==1 && one == 0:
    		two = 1
    elif two==1:
    	if n==1 && one == 0:
    		two = 0
  1
  2
  3
  4
  5
  6

• 再简化，为了使得 n==1 && one == 0 为 true，你会发现可以转换成 n&~one

•   if two==0:
    	if n&~one:
    		two = 1
    elif two==1:
    	if n&~one:
    		two = 0
  1
  2
  3
  4
  5
  6

• 到了这里你不觉得有点眼熟吗，你可以扩充完整来列出真值表

•   if two==0:
    	if n&~one:
    		two = 1 # 这个 two 就是 newtwo
    	else:
    		two = 0
    elif two==1:
    	if n&~one:
    		two = 0
    	else:
    		two = 1
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 然后得到了：

two n&~one newtwo
0   0      0   
0   1  	   1
1   0      1
1   1      0
1
2
3
4
5

• 这不就是异或吗，所以 two = two ^ (n&~one)，因为 & 优先级高于 ^ 所以小括号可以省略
• 最终代码如下

•   public int trainingPlan(int[] nums) {
    	// 因为是批量位运算，所以用了 ones 而不是 one
        int twos = 0, ones = 0;
        for(int n:nums){
            ones = (ones^n) & ~twos;
            twos = twos ^ n & ~ones;
        }
        return ones;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 我只有一个疑问，为什么别人的解法最终是：

•   public int trainingPlan(int[] nums) {
        int twos = 0, ones = 0;
        for(int n:nums){
            ones = ones^n & ~twos;
            twos = twos ^ n & ~ones;
        }
        return ones;
    }
  1
  2
  3
  4
  5
  6
  7
  8