问题
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
https://leetcode-cn.com/problems/single-number-ii/
解答
这个问题看似要记录每一个数字的出现次数。但是我看题目之前已经不幸看了题解所以知道这题一定是用位运算去做。于是问题简化成了找一个方法记录下某一位的状态，通过这一位出现次数来判断这一位的真假情况，具体次数与某一位的关系大概如下：
| 某一位出现次数 | 某一位的真值 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1（1或0皆可，我用的是1） |
| 3 | 0 |
| n（不可被3整除） | 1 |
| n（可被3整除） | 0 |
比如3这个数，二进制位分别为1，1。这个数出现第一次时我要求二进制的两位分别为11，两次时我要求二进制分别为11，三次时分别变成00。
但是当你把某一位设置为1的时候，你无法知道这是这个数出现的第一次还是第二次，所以用一个变量给每个二进制位计数看来是行不通了。这个时候我又想起了题解，看来我需要第二个变量来储存每个位是出现了第二次还是第三次。所以算法如下：
以重复的数为3为例。设变量a（记录是否出现2次）,b（记录最终剩下的位）。第一次出现3时将b的两个二进制位变成11，a的二进制位保持00（因为每个位才出现1次）。第二次出现3将b的二进制位不变，而a看到b变为了11，便知道这是第二次了，于是将自己的二进制位变成11。第三次出现3时b注意到a之后便知道是第三次了，于是将两位分别置为00，a也知道这是第三次了，也变成00。
这个算法如何实现呢？这个时候就需要利用真值表了。然后用主析取范式！
| a的位 | b的相应位 | 某数的相应位 | 结果a | 结果b |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| … | … | 0（为0时a,b无变化） | … | … |
| 0 | 0 | 1（第一次出现） | 0 | 1 |
| 0 | 1 | 1（第二次出现） | 1 | 1 |
| 1 | 1 | 1（第三次出现） | 0 | 0 |
最后b当然就是结果啦！
从这个计数器的设计这里我的第一次感觉到了离散数学是真实有用的hhh，感谢离散数学！
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 [email protected]