探寻数组中两个不重复数字的奥秘：C 语言实战之旅

在编程的世界里，经常会遇到各种各样有趣的问题，今天我们就来探讨一个经典的题目：在一个整数数组中，除了两个数字只出现一次，其余数字都出现了两次，如何高效地找出这两个只出现一次的数字呢？我们将使用 C 语言来解决这个问题，并通过详细的代码分析来深入理解其中的原理。

目录

一、问题分析 

二、代码实现与解析 

函数 fingdog 解析 

第一步：整体异或

第二步：定位关键位

第三步：分组异或

main 函数解析 

三、拓展与思考 

---

 

 

一、问题分析
 

这个问题的核心在于如何利用数组元素的特性，通过巧妙的算法来区分出那两个独特的数字。我们知道，异或运算（ ^ ）有一些非常有用的性质：任何数和 0 做异或运算，结果仍然是这个数；任何数和自身做异或运算，结果为 0；异或运算满足交换律和结合律。这就为我们解决问题提供了思路。
 

二、代码实现与解析
 

我们来看下面这段 C 语言代码：
 

c#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>// 用于找出数组中两个只出现一次的数字的函数
void fingdog(int arr1[], int sz, int arr2[]) {int ret = 0;// 第一步：对数组中所有元素进行异或操作for (int i = 0; i < sz; i++) {ret ^= arr1[i];}int pos = 0;// 第二步：找到异或结果中为 1 的最低位for (int i = 0; i < 32; i++) {if (((ret >> i) & 1) == 1) {pos = i;break;}}// 第三步：根据找到的位对数组元素进行分组异或for (int j = 0; j < sz; j++) {if (((arr1[j] >> pos) & 1) == 1) {arr2[0] ^= arr1[j];} else {arr2[1] ^= arr1[j];}}
}int main() {int arr1[] = { 1,2,3,4,5,1,2,3,4,6 };int sz = sizeof(arr1) / sizeof(arr1[0]);int arr2[2] = { 0 };fingdog(arr1, sz, arr2);printf("%d %d", arr2[0], arr2[1]);return 0;
}

函数 fingdog 解析
 

第一步：整体异或

我们定义了变量 ret 并初始化为 0，然后通过一个 for 循环遍历数组 arr1 ，将每个元素与 ret 进行异或运算。由于出现两次的数字异或后结果为 0，所以最终 ret 的值就是那两个只出现一次的数字的异或结果。

第二步：定位关键位

得到 ret 后，我们需要找到它二进制表示中为 1 的最低位。通过一个 for 循环，从右向左依次检查 ret 的每一位，当找到为 1 的位时，记录下它的位置 pos 。这个位的作用是将数组中的元素分成两组，一组该位为 1，另一组该位为 0，而那两个只出现一次的数字必然分别在这两组中。
 

第三步：分组异或

再次遍历数组 arr1 ，根据每个元素在 pos 位上的值进行分组异或。如果元素在 pos 位上为 1，则与 arr2[0] 异或；如果为 0，则与 arr2[1] 异或。这样，两组中出现两次的数字又会相互抵消，最终 arr2[0] 和 arr2[1] 就分别存储了那两个只出现一次的数字。
 

main 函数解析
 

在 main 函数中，我们定义了测试数组 arr1 ，计算其长度 sz ，并初始化用于存储结果的数组 arr2 。然后调用 fingdog 函数进行处理，最后输出结果。
 

三、拓展与思考
 

这个问题的解决方法不仅仅局限于当前的场景。从更广泛的角度看，异或运算在数据加密、错误检测等领域都有重要的应用。通过这个例子，我们可以进一步思考如何优化算法的时间复杂度和空间复杂度，比如在处理大规模数据时，如何减少不必要的计算和内存占用。
 
同时，这个问题也可以进行一些变体，例如数组中除了三个数字只出现一次，其余数字都出现两次，又该如何解决呢？这就需要我们在现有知识的基础上，进一步探索和创新算法。
 
在编程的道路上，每一个看似简单的问题背后都隐藏着无尽的知识和技巧。通过不断地实践和思考，我们才能提升自己的编程能力，更好地应对各种复杂的挑战。希望今天的分享能对你有所启发，让我们一起在代码的世界里继续探索前行！