C语言之数组数字异或

落日映苍穹つ 2022-03-21 08:46 222阅读 0赞

接着上次我们讨论的在一组数字中找出一个只出现一次的数，这次我们加大难度，在一组数字中找出两个只出现一次出现一次的数字。题目具体内容如下：一个数组中只有两个数字是出现一次， 其他所有数字都出现了两次。 找出这两个数字，编程实现。
       例如：int arr[] = {1,2,4,5,3,5,1,2}  这组数中出现一次的数字位3和4.
       思路：在上面这组数中如何找出3和4呢？我们知道这组数连续异或会得到3和4异或的结果（上篇中讨论过的），那么我们却得不到这两个数，但是我们上篇讨论过，如果这个数只出现了一次，那我们便能轻而易举的得到，所以我们得想办法将这一组数变为两组数，便就解决掉问题了，两个数不同，那么他们肯定有某一位或几位不同，那么我们便可以按照这位不同将其分类，具体实现过程如下：

#include<stdio.h>
    #include<stdlib.h>
    //函数功能 ： 找出数组中两个只出现一次的数字  
    //函数参数 ： arr为源数组，len为数组元素个数，result用来存放结果   
    //返回值   ： 无 
    void FindIsolateTwo(int *arr, int len, int *result)
    {
    	int i, all = 0, flag = 1;
    
    	for (i = 0; i < len; i++) //所有数异或  
    		all ^= arr[i];
    
    	while (!(all&flag))  //寻找过滤位  
    		flag <<= 1;
    
    	for (i = 0; i < len; i++) //利用过滤位区分  
    	{
    		if (flag&arr[i])
    			result[0] ^= arr[i];
    		else
    			result[1] ^= arr[i];
    	}
    }
    int main()
    {
    	/*一个数组中只有两个数字是出现一次，
    		其他所有数字都出现了两次。
    		找出这两个数字，编程实现。*/
    	int arr[] = {1,2,4,5,3,5,1,2};
    	int temp = 0;
    	int len = sizeof(arr) / sizeof(arr[0]);
    	int result[] = {0};
    	FindIsolateTwo(arr, len, result);
    	printf("这两个数分别是：%d %d\n", result[0], result[1]);
    	system("pause");
    	return 0;
    }