用异或实现查找只出现一次的数字

C语言中我对按位异或这种运算不太懂，通过这道题熟悉了一些相关的运算以及基本性质。

题目如下：

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次，请找出这两个数字。

首先对于这样一道题我是具体化分析比如这个数组就是{1，3，5，7，1，3，5，9}，题目要求即找出只出现一次的数字即7和9。

之前在异或那边看过这样一道题，也算是这题目的简单版本，一个数组里面只有一个数字出现一次，其他都出现两次，请找出这个数字。如何解决这样一道题？我之前想法就是用循环多次遍历，选出一个数比如叫a，再在剩下的数字里面遍历看是否有a相等的数字。这个比较繁琐，我们可以考虑用异或的性质解决，一个数字异或它自己结果为0，异或0结果为它自己即a^a=0，a^0=a，且异或满足a^b^c=a^(b^c)。因此我们可以设置一个ret异或每个数组元素，最后相同的都抵消为0，那个唯一的数字异或0为它自己即为答案。

代码如下：

int find_num_once(int a[], int n)
{
	int i = 0;
	int ret = 0;
	for (i = 0; i < n; i++) 
		ret ^= a[i];
	return ret;
}

我们还是设置一个ret异或每个数组元素，由于其它数字都出现了两次，在异或中全部抵消为0，那么最终得到的结果就是两个只出现一次的数字的异或结果ret。由于这两个数字不一样，那么这个异或结果ret肯定不为0 ，即这个结果数字的二进制表示中至少就有一位为1 。我们在结果数字中找到第一个为1 的位的位置，记为第pos 位。我们以第pos 位是不是1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第pos 位都为1 ，而第二个子数组的每个数字的第pos位都为0 。最后将子数组按照之前方法就可以分别得到各自的唯一数字。

代码如下：

#include <stdio.h> 

int main()
{
	int a[] = {1,3,5,7,1,3,5,8};
	int sz = sizeof(a) / sizeof(a[0]);
	int num1 = 0, num2 = 0;
	find_num(a, sz, &num1, &num2);
	printf("%d %dn", num1, num2);
	return 0;
}

int find_num(int a[], int n, int *pNum1, int *pNum2)
{
	int i = 0;
	int ret = 0;
	for (i = 0; i < n; i++) 
		ret ^= a[i];//ret为两个不同数字异或结果 
		
	int pos = 0;
	while (((ret >> pos) & 1) != 1) 
		pos++;
	
	for (i = 0; i < n; i++) {
		if ((a[i] >> pos) & 1== 1)//分组条件
			*pNum1 ^= a[i];
//		else
//			*pNum2 ^= a[i];
	}
	*pNum2 = ret ^ *pNum1;//ret = *pNum1 ^ *pNum2所以*pNum2 = (*pNum1 ^ *pNum2) ^ *pNum1
}

最后

以上就是糟糕发带为你收集整理的用异或实现查找只出现一次的数字的全部内容，希望文章能够帮你解决用异或实现查找只出现一次的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。