数组中仅仅出现一次的字符

题目描写叙述：

一个整型数组里除了两个数字之外，其它的数字都出现了两次。请敲代码找出这两个仅仅出现一次的数字。

输入：: 每一个測试案例包含两行：

第一行包括一个整数n，表示数组大小。
2<=n <= 10^6。

第二行包括n个整数。表示数组元素。元素均为int。

输出：: 相应每一个測试案例，输出数组中仅仅出现一次的两个数。输出的数字从小到大的顺序。

例子输入：

8
2 4 3 6 3 2 5 5

例子输出：

4 6

思路：

设a、b仅出现一次。

1.假如数组中仅仅有一个数字出现一次，其它数字均出现两次。我们能够通过异或的性质找到这个数字。由于异或有这种性质，不论什么一个数异或自己总是0。0异或不论什么数都等于不论什么数本身。

所以我们能够遍历数组。挨个异或，最后剩下的就是仅仅出现一次的数字，其它数字都被抵消了。

2.如今我们的目的是将仅仅出现一次的两个数分开，分别放到两个集合中，这样便能够利用1的结论来做。

3.我们仍然从头异或到尾。得到的结果为该数组中仅仅出现一次的两个数字的异或值（a^b）,结果必定不是0。我们能够从右向左找到a^b中第一位为1的数(二进制)，表示a和b第一个不同的位。我们依照该位是否为1将数组分成两部分。那么每一个部分均仅仅有一个数字出现一次。

代码：

/*
数组中仅仅出现一次的数字
by Rowandjj
2014/8/14
*/
#include<stdio.h>
#include<stdlib.h>
/**
 *找到数字xorVal的二进制中第一个值为1的位
 *
 */
int FirstBitIs1(int xorVal)
{
	int index = 0;
	while(((xorVal&1)==0) && (index < 8*sizeof(int)))//不能越界,注意运算符优先级。多加几个括号
	{
		index++;
		xorVal = xorVal>>1;
	}
	return index;
}
/**
 *推断data中第index位（二进制）是否为1
 */
bool isBit1(int data,int index)
{
	data = data>>index;
	return data&1;
}
/**
 * data 目标数组
 * len  数组长度
 * num1 一个仅仅出现一次的数字
 * num2 还有一个仅仅出现一次的数字
 */
bool FindNumberAppearOnce(int data[],int len,int *num1,int *num2)
{
	if(data == NULL || len < 2)
	{
		return false;
	}
	int i;
	int xorVal = 0;
	for(i = 0; i < len; i++)
	{
		xorVal ^= data[i];
	}
	
	int indexOf1 = FirstBitIs1(xorVal);
	*num1 = *num2 = 0;//一定要赋值为0
	for(i = 0; i < len; i++)
	{
		if(isBit1(data[i],indexOf1))
		{
			*num1 ^= data[i];
		}else
		{
			*num2 ^= data[i];
		}
	}
	return true;
}
int main()
{
	int n;
	while(scanf("%d",&n) != EOF)
	{
		if(n <= 1)
		{
			continue;
		}
		int *arr = (int*)malloc(sizeof(int)*n);
		if(!arr)
		{
			exit(-1);
		}
		int i;
		for(i = 0; i < n; i++)
		{
			scanf("%d",arr+i);	
		}
		int num1,num2;
		if(FindNumberAppearOnce(arr,n,&num1,&num2))
		{
			if(num1 < num2)
			{
				printf("%d %d
",num1,num2);
			}else
			{
				printf("%d %d
",num2,num1);
			}
		}
		free(arr);
	}
	return 0;
}

上面代码能够再优化下，有这种一个性质：a&(-a)将会把a的二进制形式中最右边的1保留，其它位置0.比方10（1010）&-10（0110） = 0010。

代码：

/*
数组中仅仅出现一次的数字
*/
#include<stdio.h>
#include<stdlib.h>
bool FindFirstAppearOnceNum(int data[],int len,int *num1,int *num2)
{
	if(data == NULL || len <= 1)
	{
		return false;
	}
	int i;
	int xorVal = 0;
	for(i = 0; i < len; i++)
	{
		xorVal ^= data[i];
	}
	*num1 = *num2 = 0;//一定要赋值为0
	int temp = xorVal & (-xorVal);//结果：xorVal中最右边的1被保留其它位为0
	for(i = 0; i < len; i++)//遍历数组。将数组分成两部分。每一部分仅仅有一个数字出现一次
	{
		if(data[i] & temp)//temp中某一位为1。其它位为0。再与上data[i]就能够将两个仅仅出现一次的数字分开
		{
			*num1 ^= data[i];
		}else
		{
			*num2 ^= data[i];
		}
	}
	return true;
}
int main()
{
	int n;
	while(scanf("%d",&n) != EOF)
	{
		if(n <= 1)
		{
			continue;
		}
		int *arr = (int*)malloc(sizeof(int)*n);
		if(!arr)
		{
			exit(-1);
		}
		int i;
		for(i = 0; i < n; i++)
		{
			scanf("%d",arr+i);
		}
		int num1,num2;
		if(FindFirstAppearOnceNum(arr,n,&num1,&num2))
		{
			if(num1 < num2)
			{	
				printf("%d %d
",num1,num2);
			}else
			{
				printf("%d %d
",num2,num1);
			}
		}
		free(arr);
	}
	return 0;
}