一. 簡介

前面兩篇文章解決力扣網上"查找重復數"的題目，提供了三種思路：哈希表、二分法和快慢指針。文章如下：

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