一. 简介
前面两篇文章解决力扣网上"查找重复数"的题目，提供了三种思路：哈希表、二分法和快慢指针。文章如下：
力扣网C语言编程题：快慢指针来解决 “寻找重复数”-CSDN博客
本文提供另一种解题思路：位运算来解决。
二. 力扣网C语言编程题：位运算来解决 “寻找重复数
题目：位运算来解决 "寻找重复数"
给定一个包含 n+1n+1 个整数的数组 numsnums，这些整数在 11 到 nn 之间（包括 11 和 nn），其中有一个整数出现了两次，其余整数均只出现一次。找出这个重复的整数。
题目分析：（位运算）
这个方法我们来将所有数二进制展开按位考虑如何找出重复的数，如果我们能确定重复数每一位是 1 还是 0 就可以按位还原出重复的数是什么。
考虑第 i 位，我们记 nums 数组中二进制展开后第 i 位为 1 的数有 x 个，数字 [1,n] 这 n 个数二进制展开后第 i 位为 1 的数有 y 个，那么重复的数第 i 位为 1 当且仅当 x>y。
举例说明：
以示例 1 为例，如下的表格列出了每个数字二进制下每一位是 1 还是 0 以及对应位的 x 和 y 是多少：
正确性的证明的方法，可以考虑不同示例数组中第 i 位 1 的个数 x 的变化：
如果测试用例的数组中 target 出现了两次，其余的数各出现了一次，且 target 的第 i 位为 1，那么 nums 数组中第 i 位为 1 的个数 x 恰好比 y 大一。如果 target 的第 i 位为 0，那么x == y。
如果测试用例的数组中 target 出现了三次及以上，那么必然有一些数不在 nums 数组中了，这s时相当于我们用 target 去替换了这些数，则有如下情况对 x 的影响：
(1) 如果被替换的数第 i 位为 1，且 target 第 i 位为 1：x 不变，满足 x>y。
(2) 如果被替换的数第 i 位为 0，且 target 第 i 位为 1：x 加一，满足 x>y。
(3) 如果被替换的数第 i 位为 1，且 target 第 i 位为 0：x 减一，满足 x≤y。
(4) 如果被替换的数第 i 位为 0，且 target 第 i 位为 0：x 不变，满足 x≤y。
总结：
也就是说如果 target 第 i 位为 1，那么每次替换后只会使 x 不变或增大，如果为 0，只会使 x 不变或减小，始终满足 x>y 时 target 第 i 位为 1，否则为 0，因此，我们只要按位还原这个重复的数即可。
解题思路四：
1. 首先，计算最大可能位数（假设使用32整数）
2. 遍历每一位，创建一个掩码（为了统计第bit位上是否为1时判断使用，也为了后面某个位置1时使用）；
3. 计算理论上该位出现的次数（即[1,n]都出现一次时的情况）；计算实际数组中该位出现的次数（实际数组元素，有重复数字）；
4. 如果实际次数 >理论次数，则说明重复数的该bit位则为1；
C语言实现如下：
//位运算
int findDuplicate(int* nums, int numsSize){
if((nums == NULL) || (numsSize <= 0)) {
return -1;
}
int i;
int bit;
int duplicate = 0;
int n = numsSize-1;
int mask = 0; //当前位的掩码
int expected = 0;
int actual = 0;
//首先，计算最大可能位数（假设使用32整数）
int max_bit = 0;
while((1 << max_bit) <= n) {
max_bit++;
}
//遍历每一位
for(bit = 0; bit <= max_bit; bit++) {
//每一位的掩码
//（为了统计第bit位上是否为1时判断使用，也为了后面某个位置1时使用，所以，1 << bit）
mask = 1 << bit;
//计算理论上该位出现的次数（即[1,n]都出现一次时的情况）
for(i = 1; i <= n; i++){
if(i & mask) {
expected++;
}
}
//计算实际数组中该位出现的次数（实际数组元素，有重复数字）
for(i = 0; i < numsSize; i++) {
if(nums[i] & mask) {
actual++;
}
}
//如果实际次数 >理论次数，则说明重复数该位则为1
if(actual > expected) {
duplicate |= mask;
}
expected = 0;
actual = 0;
}
return duplicate;
}这里在实现过程中要注意，每完成一次第 i位的运算，需要将统计1个数的两个计数器清零。
可以看出时间复杂度：O(nlogn)。
（O(logn) 代表了我们枚举二进制数的位数个数，枚举第 i 位时需要遍历数组统计 x 和 y 的答案，这个过程时间复杂度为O(n)，因此总时间复杂度为 O(nlogn)。）