欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

找出数组中两个只出现一次的数字

程序员文章站 2022-07-15 11:59:29
...

题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字

通过这道题感觉位运算很强大~这道题利用异或的几个性质:任何数与其本身异或值都为0,异或运算满足交换律。因此将一组数依次异或,若里面只有一个只出现一次的数,其他的数都出现两次,则最后的结果必然是那个只出现一次的数。要找到两个数字就可以先通过异或整个数组,将得到的结果分组。然后依次安组异或就可以得到所求的值~

代码如下:

#include<iostream>
using namespace std;
int findFirstOne(int value);
bool testBit(int value,int pos);
int findNums(int date[],int length,int &num1,int &num2){
	if(length<2){return -1;}
	int ansXor=0;
	for(int i=0;i<length;i++){
		ansXor^=date[i];               //异或
	}
	int pos=findFirstOne(ansXor);
	num1=num2=0;
	for(int i=0;i<length;i++){
		if(testBit(date[i],pos))
			num1^=date[i];
		else
			num2^=date[i];
	}
	return 0;
}
int findFirstOne(int value){     //取二进制中首个为1的位置
	int pos=1;
	while((value&1)!=1){
		value=value>>1;
		pos++;
	}
	return pos;
}
bool testBit(int value,int pos){  //测试某位置是否为1
	return ((value>>pos)&1);
}
int main(void){
	int date[10]={1,2,3,4,5,6,4,3,2,1};
	int ans1,ans2;
	if(findNums(date,10,ans1,ans2)==0)
		cout<<ans1<<" "<<ans2<<endl;
	else
		cout<<"error"<<endl;
	return 0;
}

转载于:https://www.cnblogs.com/aLittleBitCool/archive/2011/04/14/2015720.html