如何用位运算在数组中找到仅出现一次的元素 c++位运算解决方案

### 使用 C++ 位运算找到数组中唯一出现一次的元素 在解决此类问题时，可以利用 **XOR 运算** 的特性来高效处理。以下是具体方法： #### 方法一：单个数字仅出现一次的情况 对于一个数组中除了某个数字外其余所有数字均出现两次的情形，可以通过 XOR 运算快速定位该唯一的单一数字。 XOR 运算具有如下性质： - `a ^ a = 0` （任何数与其本身异或结果为零） - `a ^ 0 = a` （任何数与零异或结果为其本身） 因此，遍历整个数组并对其中的所有元素执行 XOR 操作即可得到最终的结果[^1]。 ```cpp class Solution { public: int singleNumber(std::vector<int>& nums) { int result = 0; for(auto num : nums){ result ^= num; // 对每个元素进行异或操作 } return result; // 返回最后剩下的那个唯一值 } }; ``` 此算法的时间复杂度为 O(n)，空间复杂度为 O(1)[^1]。 --- #### 方法二：两个数字各出现一次的情况 当存在两个独立的数值各自只显现一次而其它全部成双呈现的时候，则需进一步扩展逻辑。首先依旧采用整体 XOR 来获取这两个特殊值之间的差异点；接着依据某一位上的区别把原始数据分割开来再分别做 XOR 处理从而分离出目标值们[^2]。 下面是基于这种方法的具体实现代码片段: ```cpp #include <stdio.h> #include <stdlib.h> void findTwoNumbers(int* src, int n, int* pNum1, int* pNum2){ int xorSum = 0; /* Step 1: Compute the overall XOR */ for(int i=0;i<n;i++) xorSum ^= src[i]; /* Step 2: Find out which bit is set between two unique numbers*/ unsigned int pos = 0; while(((xorSum >> pos) & 1)==0) ++pos ; /* Initialize both results as zero */ *pNum1=*pNum2=0; /* Separate and compute individual values based on differing bits */ for(int j=0;j<n;++j){ if((src[j]>>pos)&1){ (*pNum1)^=src[j]; }else{ (*pNum2)^=src[j]; } } } int main(){ int arr[]={1,1,2,3,4,5,6,6,7,7}; int num1,num2; findTwoNumbers(arr,sizeof(arr)/sizeof(*arr),&num1,&num2); printf("The non-repeating elements are %d and %d\n",num1 ,num2 ); } ``` 这里的关键在于如何区分那两位独一无二的整型变量——通过检测它们之间第一个不同的比特位完成分类并再次运用之前提到过的简单版本的技术得出结论[^2]. --- #### 方法三：有序数组中的特殊情况 如果给定的是已排序好的序列，并且知道除了一项之外每一对连续项目都是完全一样的情况下的解法会更加简洁明了一些。我们能够借助二分查找配合按位计算技巧迅速锁定答案所在区域[^3]: ```cpp class Solution { public: int singleNonDuplicate(std::vector<int>& nums) { int left = 0, right = nums.size()-1; while (left < right){ int mid = left + ((right-left)>>1); if(nums[mid]==nums[(mid^1)]){ left = mid+1; } else{ right = mid; } } return nums[left]; } }; ``` 在这个变体里边主要依赖于观察到的事实就是说只要保持住当前考察范围内的长度始终维持在一个奇数状态的话那么必然有一个单身汉藏匿于此区间之中[^3]。 --- ### 总结 以上介绍了三种不同场景下应用 C++ 中的位运算技术去发现那些隐藏起来仅仅现身过一次的数据成员的办法。无论是面对无序列表还是已经排列整齐待检视的对象集合都能够游刃有余地解决问题。