问个算法题

模拟三机制的亦或

LeetCode No137：https://leetcode.com/problems/single-number-ii/ 异或可以理解为1位不带进位的二进制加法， 即：0+0=0；0+1=1；1+0=1；1+1=0（1+1=10，进位的1忽略即为0） 所以如果其他数字出现2次，只有一个数字出现一次， 那么把所有的数字异或一遍，出现两次的数字每一个bit都会进位变成0， 最后的结果就是单独的哪个数字； 如果其他数字出现三次的话，同样的思路，我们考虑2位的不带进位的二进制加法， 即：00+01=01；01+01=10；10+01=11；11+01=00； 但是两位的二进制加法要加四次才能变成0，题目里的数字只出现了3次， 所以这里需要手动去掉一次加法：00+01=01；01+01=10；10+01=00， 即保证你的算法在一个bit位上经过3个1以后会变成0 这个思路理论上可以用于处理任意次数的数字， 其他数字出现2次需要1个临时变量，出现3-4次需要2个临时变量， 出现5-8次需要3个临时变量，出现9-16次需要4个临时变量……依此类推 可以参考这个帖子：https://discuss.leetcode.com/topic/2031/challenge-me-thx/18 The code seems tricky and hard to understand at first glance. However, if you consider the problem in Boolean algebra form, everything becomes clear. What we need to do is to store the number of '1's of every bit. Since each of the 32 bits follow the same rules, we just need to consider 1 bit. We know a number appears 3 times at most, so we need 2 bits to store that. Now we have 4 state, 00, 01, 10 and 11, but we only need 3 of them. In this solution, 00, 01 and 10 are chosen. Let 'ones' represents the first bit, 'twos' represents the second bit. Then we need to set rules for 'ones' and 'twos' so that they act as we hopes. The complete loop is 00->10->01->00(0->1->2->3/0). For 'ones', we can get 'ones = ones ^ A[i]; if (twos == 1) then ones = 0', that can be tansformed to 'ones = (ones ^ A[i]) & ~twos'. Similarly, for 'twos', we can get 'twos = twos ^ A[i]; if (ones* == 1) then twos = 0' and 'twos = (twos ^ A[i]) & ~ones'. Notice that 'ones*' is the value of 'ones' after calculation, that is why twos is calculated later. Here is another example. If a number appears 5 times at most, we can write a program using the same method. Now we need 3 bits and the loop is 000->100->010->110->001. The code looks like this: 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; } Or even like this: int singleNumber(int A[], int n) { int twos = 0xffffffff, threes = 0xffffffff, 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; }

【 在 dss886 的大作中提到: 】 : LeetCode No137：https://leetcode.com/problems/single-number-ii/ : 异或可以理解为1位不带进位的二进制加法， : 即：0+0=0；0+1=1；1+0=1；1+1=0（1+1=10，进位的1忽略即为0） : ................... 感谢，我看看~~[ema4][ema4]

思路看懂了，运算符看不懂 :