整型数组里只出现一次的数字--[c语言笔试题]

找出数组内只出现一次的数字，是一系列的笔试题，来考察大家对位运算的掌握，下面我们从最简单的开始来看看吧！

一、题目：一个整型数组里只有一个数字出现了一次，其余数字都出现了两次，请写程序找出出现了一次的数字。
  如：{1，2，1，2，3}，找出1

看到这个题目时，我们容易想到异或运算的性质。异或运算相同为0，相异为1，则：

a^a = 0; (1)

0^a = a; (2)

a^b^a = b; (3)

通过以上前两式，以上数组里两两相同的异或结果为0，0在与只出现一次的那个数字异或就会得到这个数字,你也可以通过3

式想，1^2^1 = 2, 2^2 = 0,0^3 = 3,还是找到了我们想要的数。不管怎么想，我们都得到统一的思路：将数组里面所有的数字异或一遍，最终得到的那个数字就是只出现一次的数。

[c语言代码]：

int FindAppearOnce(int arr[], int len)
{
	int i = 0;
	int ret = 0;
	for(i = 0; i<len; i++)
	{
		ret = arr[i]^ret;
	}
	return ret;
}

二、题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个只出现一次的数字。
  如：{1，2，1，2，3，4}，找出3和4

有了上道题的铺垫，我们来整理一下这道题的思路：

第一步，将数组中所有数字异或一遍，得到的结果为两个只出现一次的数字的异或结果

              本题为：0011(3)^(0100)4  =  0111(7)  括号内为十进制

第二步，在第一步得到的数字的二进制中找出第一个为1的位，通过这个位为0或为1，将数组中的数字分为两组。这两个组里出现一次的两个数必定不在同一组，两个相同的数字必定会被分在一个组。

             本题0111最低位就为1，将数组中最低位为1的放在一组，为0的放在另一组，则3和4必定不在同一组，因为找出的这  个位为1，即3和4 的这一位不同。则一组为：1，1，3 二组：2，2，4

第三步，将两个组中的所有数字分别异或，就会得到每个组中只出现一次的那个数。（思想同第一题）

             本题1^1^3 = 3，2^2^4 = 4，所以就找到了只出现了一次的两个数。

[c语言代码]：

void FindAppearOnce(int arr[], int len, int* pn1, int* pn2)
{
	int num = 0;//记录整组异或的结果，即两个一次出现的数异或的结果
	int i = 0;
	int k = 1;

	for(i = 0; i<len; i++)  //得出整组异或的结果，即两个一次出现的数异或的结果
	{
		num = num^arr[i];
	}

	while(num&1 != 1)    //找出异或结果中第一个为1的bit位
	{
		k++;
		num = num>>1;
	}

	for(i = 0; i<len ; i++)//将原数组分为两组，分别求出每组中出现一次的数字
	{
		int k_bit = (arr[i]>>(k-1)) & 1; //arr[i]第k位的值
		if(k_bit == 1)
		{
			*pn1 = *pn1^arr[i];
		}
		else
		{
			*pn2 = *pn2^arr[i];
		}
	}

}

大家实现的时候可以根据功能分几个函数。

谢谢阅读！！

最后

以上就是平常火车为你收集整理的整型数组里只出现一次的数字--[c语言笔试题]的全部内容，希望文章能够帮你解决整型数组里只出现一次的数字--[c语言笔试题]所遇到的程序开发问题。

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