1. 初级版
描述：一个整型数组里除了1个数字之外，其他的数字都出现了两次，请写程序找出这个只出现一次的数字。
思路：利用异或的特性，x^y^x=x^x^y=y。对数组所有元素进行一次异或操作，最后得到的就是只出现一次的数字。
1.1变化版
描述：一个整型数组里除了2个数字之外，其他的数字都出现了两次，请写程序找出这两个只出现1次的数字。
思路：
1. 两个数字肯定是不同的，则必有某一位上，两个数字是不同的；
2. 可以对数组所有元素进行一次异或操作，得到两个数字哪一位是不同的；
3. 然后根据这一位将整个数组分为两个数组，则两个数会分在不同的数组，并且相同的数一定会分在同一个数组；
4. 之后利用异或的方式得到数字。
2. 进阶版
描述：一个整型数组里除了1个数字之外，其他的数字都出现了三次，请写程序找出这个只出现一次的数字。
思路：最基本的工具还是利用异或的特性，但在使用方法上要做一些改变。
用两个数字s1,s0记录每一位1的个数（s1为高位数，s0位低位数），如果等于3（即011）则置零。设s1_k为高位数的第k位、s0_k为低位数的第k位，A_k为其中一个数的第k位：
则满足：
输入 |
输出 |
|
|||
S1_k |
S2_k |
A_k |
S1_k |
S2_k |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
等于3（011），清零 |
1 |
1 |
0 |
0 |
0 |
不可能出现输入为s1s0=11的情况，因为一出现就已经置零，此时s1s0的值为任意值，不影响结果；为方便起见，记s1s0=00，便于理解。 |
1 |
1 |
1 |
0 |
0 |
|
得到：
s1 = (~s1 & ~s0 & A) | (~s1 & s0 & ~A);
s0= (~s1 & s0 & s0) | (s1 & ~s0 & ~A);
利用上述公式，对数组所有元素进行操作，最后得到的s0就是只出现一次的数字。
3. 推广版
描述：给出一个整型数组，每个元素都出现 k （k>1）次，只有一个元素出现 p 次（p >= 1，p % k != 0）。找到这个单独的元素。
思路：大体而言，还是利用异或的特性，还有计数器的思想。
无论是异或，还是计数器的思想，在大学课程中学过数电的人肯定不会陌生。事实上，如果我们使用位操作来解决问题，那么我们的思考方式就是之前我们学过的知识，毕竟，计算机的底层就是用“位”的概念来实现的。
关于此问题的详细推导过程可以参考算法题总结之找到数组中出现次数唯一不同的数字一文。
（http://blog.csdn.net/cloudox_/article/details/70172475）
在此，只是简单地描述一下使用计数器的思路，便于理解。
首先，针对每一位，用一个计数器来统计1出现的次数，次数达到k则置零，这样每个出现k次的元素，经过计数后最终的结果一定是0。（若某一位上是0，不影响结果）
然后，需要构建一个k位的计数器，若有m-1 < log k ≤ m，则至少需要m个数来表示一个k位计数器，假设m个数为Sm,Sm-1,……,S2,S1。（p的大小无影响）
如果元素共有n位，
|
|
N-1位 |
N-2位 |
|
1位 |
0位 |
|
Sm-1 |
|
|
|
|
|
|
Sm-2 |
|
|
|
|
|
|
|
|
|
…… |
|
|
|
S1 |
|
|
|
|
|
|
S0 |
|
|
|
|
|
代表1个数 |
|
|
|
|
|
代表1个计数器 |
|
|
1. 每一行（蓝色）代表1个数。 2. 每一列（黄色），代表1个计数器；m个数的第0位联合起来就是第0位上的计数器。 3. 通过m个数，得到了n个k位计数器。 |
||||||
当计数器位数较少时，我们还可以采用上一节（2.进阶版）的方法，手动计算出所需的公式，但计数器位数较多时，这种方法就不合适了。
在此，我们借鉴最朴素的计数思想，对于一个二进制数，只有当第0位到第i-1位均为1，且添加到第0位的数也为1时，第i位的数才会发生变化。设新来的数位A，则上述过程用数学公式可以描述为：
Si = Si ^ ( Si-1 & Si-2 & …… & S1 & S0 )
当计数器计数到k时，将其置零。即 Sm-1,Sm-2,……,S2,S1,S0为k的二进制表述时，令每一位均置零。
令F = f ( Sm-1,Sm-2,……,S2,S1,S0 ) ，当且仅当Sm-1,Sm-2,……,S2,S1,S0为k的二进制表述时，F=0：
则对于每一位，有：Si = Si & F。
最后，则是利用所得计数器还原我们寻找的次数不同的那个数。
对于重复k次的数，在计数器中的结果一定是全零，对计数器的结果无影响，所以计数器的结果就只与重复p次的那个数有关。
如果单独元素的某一位为1，则相应位的计数器的值一定为p；
如果单独元素的某一位为0，则相应位的计数器的值为0。
也就是说计数器的值只有两种结果，0或p。
假设单独元素的第i位、第i+1位、第j位为1，第i-1位、第j-1位、第j+1位为0，p可以描述为0……1011，则可以有：
|
…… |
i+1位 |
i位 |
i-1位 |
…… |
j+1位 |
j位 |
j-1位 |
…… |
Sm-1 |
|
0 |
0 |
0 |
|
0 |
|
|
|
…… |
|
|
|
|
…… |
|
|
|
|
S3 |
|
1 |
1 |
0 |
|
0 |
1 |
0 |
|
S2 |
|
0 |
0 |
0 |
|
0 |
0 |
0 |
|
S1 |
|
1 |
1 |
0 |
|
0 |
1 |
0 |
|
S0 |
|
1 |
1 |
0 |
|
0 |
1 |
0 |
|
|
|
|
等于p |
|
|
等于0 |
|
|
|
|
计数器不为0，则表示单独元素相应位为1；否则为0。由此得到下面的结果 |
||||||||
|
|
1 |
1 |
0 |
|
0 |
1 |
0 |
|
|
1. 可以发现，最终得到的结果（紫色）和p的二进制表述的非零位上对应的数字（蓝色）一致； 2. 也就是说，我们可以直接用p的二进制表述非零位对应的数字来作为最终结果。 |
|||||||||
最后，补充一种特殊情况：如果单独元素为0，则计数器的结果均为0；反之也成立。