当前位置:网站首页>C语言位运算高效解决数字出现的次数

C语言位运算高效解决数字出现的次数

2020-12-08 12:50:14 osc_9bmcw8wc

题目描述

如下图所示:找出只出现一次的两个数字,其余都出现了两次。
在这里插入图片描述

题目分析

从整形数组中找出只出现一次的数字,其余都出现了两次。

分析

  1. 用 0 异或所有数组中元素,找出出现一次的两个数。
    记:temp=0^ 3^ 2^ 3^ 6=2 ^ 6=4(二进制形式:0100)

  2. 找分离temp的分离标志,sep = temp & (-temp )。4&(-4)=4(0100),其中-4在内存中是以补码存储的哦,不要弄错了。

    判断语句:4 & 2 (0100^0010)= 0(0000) 为零,则跳过,不执行下面语句。
    4 & 6(0100&0110)=4(0100)不为零,执行下面语句,找出第一个出现一次的数。
    num[0]=0^ 2 (0000^0010)= 2(0010) 此时分离出来了2。

  3. 分离出来第二个元素。
    num[1]=temp^ num[1]=4^ 2 (0100^0010)=6 (0110)。

参考代码

//0^任何都为任何数,出现两次的数字被异或除掉,只剩出现一次的数字
//分离出来只剩下两个数字异或的内容
	for (i = 0; i < numsSize; i++){
		temp = temp ^ nums[i];
	}
//接下来两个不同的数字的异或中分离出来 不同的数字
	sep = temp & (-temp );

//提取第一个数字
	for (i = 0; i < numsSize; i++){
		if (0 != (nums[i] & sep)){
			x = x ^ nums[i];//分离出来第一个数
		}
	}
	//提取第二个数字
	y = temp ^ x;//分离出来一个数
	num[0] = x;//保存找到的出现一次的数
	num[1] = y;

总结

以上是我学习的简单总结,如果有不好请各位大佬提出,我即时改正。

版权声明
本文为[osc_9bmcw8wc]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4296417/blog/4780913