一. 简介

前面两篇文章解决力扣网上"查找重复数"的题目，提供了三种思路：哈希表、二分法和快慢指针。文章如下：

力扣网C语言编程题：“寻找重复数”的两种思路-CSDN博客

力扣网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)。）