花式位运算：找出只出现了一次的数

昨天老大甩过来一个Leetcode算法题，第二问想了有点久，第三问被虐到查了答案醍醐灌顶，总结分享一下。                   

我这儿只讨论位运算的骚操作，有其他有意思的解法欢迎分享❤️

Q1, Given an array of integers, every integer appears twice except for one, find this outlier. 

这个比较简单，一路XOR一遍就完了。这里用到了XOR操作服从交换律的这一性质，出现两次的数字会xor到0，只出现一次的数字就留到了最后返回。

Q2, what if every integer appears three times except for one?

开始tricky了。从第一问过渡过来，很自然地会想，有没有一种可能的位运算操作或者位运算操作组合，遇到同一个元素三次会被置为0呢？试了多种排列组合以后觉得这个思路有点凉。。

如果不能直接拿到每个数字出现的次数，考虑一下拿到每个位上1出现的次数mod 3的结果。要求一个linear time algo，每拿到一个数要somehow更新一下结果，那么问题就来了：更新什么结果、怎么更新呢？

有点streaming algorithm的意思。说到streaming algo就想到了老Rao，然后就想到了他回回强调的” structure of the solution”。那就来看要return的数的structure：假设见完了array里所有整数应该return1001，意味着右数第1和第4这两个位置，见过了1(mod 3) 次1。那么这就清晰了，我们来记录每个bit位见过1的次数吧，每见3次一清零。

所以开了三个flag数：flag1, flag2, flag3. flag_k中为1的位置代表 之前见过的所有数中 在这个位置上 1出现过k次。那么当拿到一个新整数n的时候，有一些位置上见到了新的1，我们来更新这三个flag。

开个栗子说吧。假设flag1 = 10001, flag2 = 01001, flag3 = 00010, 这时候下一个数n拿到了10001。看flag2：flag2最低位是1意味着之前见过的数中1在这一位出现过2(mod 3)次，而新数n在这一位上是1，意味着现在这一位见过3 = 0 (mod 3) 次1 了，所以要给flag3补上这一位的1（flag3 = flag2 & n=01001 & 10001 = 00001)。既然这一位上现在见过3次了，那么要把它从flag2里删掉（flag2 ^= flag3 = 01001 ^= 00001 = 01000)。用类似的逻辑从flag1来update flag2 -- n 和 flag1 中都是1的位置，就说明现在见过2（mod 3）次了（flag2 |= flag1 & n = 01000 | (10001 & 10001) = 11001。 思考题： 为什么这里是用了一次or)？最后更新 flag1 -- n中为1而flag1中不为1的位置要补作1，都为1的位置刚才被update到flag2里了，现在从flag1里删掉（flag1 ^= n =10001 ^ 10001=00000）。 这一次update要小心，因为，n中为1而flag1中不为1的位置，有可能是之前出现过两次，现在已经出现过三次了的，所以最后还要从flag1里去掉这些部分（flag1 ^= flag3）。

tldr: 用flag_k=flag_{k-1} & n来update每个flag，然后flag_{k-1}=flag_{k-1} & (flag_{k})删掉被upgrade过的位。举个栗子，比方说第3位上1出现了两次，correspondingly flag2的第三位上就是1。接下来拿到的新数字n的第三位有1的话，那就把flag3的第三位置为1，相应的把flag2的第三位上的1删掉。

花式位运算：找出只出现了一次的数

#ShutUpAndShowMeTheCode️️️

第二问就完了。

补充一个只用两个flag数的非常elegant的implementation。先上码：

a & ~b本质上是从a里删掉b中有的东西。整数n第一次出现的时候会被记录在flag1里面，第二从出现会被从flag1里抹掉，转而被记录在flag2里，第三次出现会被flag2里抹掉，两个flag就都清零了。所以一个只出现了一次的数最后会留在flag1里。

和上一个算法相比都是六次bit operations per iteration, 但是这个就好写又漂亮多了。

Q3: what if every element appears exactly twice but two?

俩outliers怎么办？Denote这俩数字为m and n. 一路XOR操作我们能拿到 flag = m ^ n. 因为m != n, 这个flag必不为0，进一步讲，flag里为1的位置意味着m和n在这一位上不一样。这个结果怎么用呢？这里关键的一个观察是，所有数里面，要么在这一位为1要么为0，我们可以靠这个criteria把所有数分到两个set里面, m^n^m = n, m^n^n = m, 这两个sets分别去跟flag作xor跑Q1的算法就得到了我们要的结果.

于是这一问的关键就是拿到flag里一个为1的位。说起来找一个数第一个不为0的位置是上学期61B一次homework原题： flag ^ ~(flag - 1)。

其实如果不强求space complexity的话，这三问都可以哈希给个O(n)的解法， 或者sort一遍given array然后比较相邻元素给出O(nlogn)的解法，就很trivial啦。不过看看位运算的解法还是挺有意思的嘿嘿。

就酱～