为何通过位计数取模x可找出xn+1个数中的唯一数？

给定数组示例：[7,6,7,6,5,7,6]，其中除唯一数5外，其余数7和6均重复3次（即x=3）。下面直白拆解这个方法的原理：

先看示例的实际运算过程 #

把数组中每个数的二进制按位对齐排列（补前导零保证位数一致）：

7 → 1 1 1
6 → 1 1 0
7 → 1 1 1
6 → 1 1 0
5 → 1 0 1
7 → 1 1 1
6 → 1 1 0

统计每一列（从左到右对应二进制高位到低位）的1的数量：

• 第1列：7个1
• 第2列：6个1
• 第3列：4个1

对每列的统计结果取模x=3：

• 第1列：7 % 3 = 1
• 第2列：6 % 3 = 0
• 第3列：4 % 3 = 1

把结果按顺序组合就是101，对应十进制的5，也就是数组中的唯一数。

核心原理拆解 #

这个方法的本质是利用重复x次的数，其每一位二进制1的总出现次数必然是x的倍数：

• 如果某个重复数的某一位是1，那它会在这一列贡献x个1（因为重复x次），总数是x的倍数；
• 如果这个重复数的某一位是0，那它在这一列贡献0个1，总数也是x的倍数。

而唯一数的存在会打破这个倍数关系：

• 若唯一数的某一位是1，那这一列的总1数 = 重复数贡献的x倍数个1 + 1，取模x后结果为1，对应唯一数的这一位是1；
• 若唯一数的某一位是0，那这一列的总1数 = 重复数贡献的x倍数个1，取模x后结果为0，对应唯一数的这一位是0。

这样每一列取模后的结果，就正好拼出唯一数的二进制表示，转成十进制就是我们要找的数。

内容的提问来源于stack exchange，提问作者Szyszka947