微波EDA网,见证研发工程师的成长!
首页 > 硬件设计 > 嵌入式设计 > 异或运算在算法中的经典运用

异或运算在算法中的经典运用

时间:12-01 来源:互联网 点击:
“一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字?”这是经典的算法题,乍看这个题的思路特别多。

比如首先排序、然后在查找不同的数据就能找到这两个数字,这种实现方法的时间复杂度应该是在O(NlgN),因为比较排序的算法最好的时间复杂度就是这样。但是乍一看,这题就解决了,但是还没有充分运用一个条件,绝大多数元素是成对出现的,这个条件的作用是什么呢? 当然还有的思路就是hashmap实现,这种实现方法就是采用hash表存储每个变量的次数,最后遍历hash表即可,但是这种方法也存在问题,如果存在负数,或者数组元素的值特别大,采用Hashmap实现的空间复杂度太大,并不是我们需要的解决方式,hashmap适合的方式是在一定范围类的数值进行统计。上面这两种方法可能是比较快速想到的。

这道题的实现方法很多,关键是找到最好的实现方法很难,本文就介绍采用异或运算实现这道题目的解法。

异或运算是C语言中位运算的一种操作,这种操作对于嵌入式程序员可能比较熟悉,但是对于一般的程序员可能运用的比较少,异或操作具有如下的特征:

0^num = num; 1^num = ~num; num ^ num = 0; 其中num = 0或者1。

运用结合律等特征有:

a^a^b^b^c = (a^a)^(b^b)^c=0^0^c=c;

需要注意:如果有a + b = c; 则有可能使得a ^ b ^ c = 0;这个条件是非充分非必要,比如a = 1,b = 2, c = 3,这时候的a ^ b ^ c = 0是成立的,但是a = 2, b = 2, c = 4,则是不成立的。

从上面的结合律可以知道如果两个相同的数进行异或操作结果是0,根据题目中元素是成对出现的,可以充分运用异或操作的结合特性,数组元素异或以后的结果肯定会包含两个不成对元素的特征。

假设数组元素为a[N],其中N的值很大,不成对的元素为an,am。实现上述过程的步骤如下所示:

首先,变量元素对所有元素进行异或操作,得到的结果肯定是an^am。也就说通过异或操作以后,结果中保存了an和am的特征。由于am和an不同,am^an的结果肯定是大于等于1。am和an不同,那么am^an中为1的某一个bit肯定是am或者an中某一个的特征。

然后,定义两个值num1,num2,分别用来计算an、am,选择am^an中的某一个bit作为特征位,假设是第K位是特征位,再次对元素进行遍历,如果元素的第K位是1,这个元素可能是am或者an,那么将当前元素与num1进行异或操作,如果元素的第K为不为0,那么这个元素则可能是另一个值,那么将当前元素与num2进行异或操作。这样遍历完所有元素,因为大部分数据成对出现,根据异或运算的特征,num1,num2就分别保存了两个不同的值。

由上面的分析可知,这种算法只需要遍历两次数组空间即可实现数据的判定,这样时间复杂度为O(N),同时因为没有hashmap之类的结构体,这样空间复杂度就是O(1)。这种算法的实现肯定是最佳的。相比前面提到的hashmap、排序算法时间复杂度和空间复杂度都要小,因此这种算法的实现应该是最佳的。

代码实现如下:

#include
#include

int whichbitone(int in)
{
int i = 0;

while((in & (1 < i)) == 0)
i ++ ;

return i;
}

int isbitone(int in, int k)
{
if((in & (1 < k)) != 0)
return 1;
else
return 0;
}

void xortest(int *array, int size)
{
int dxor = 0, xor = 0;
int i = 0, j = 0;
int num1 = 0, num2 = 0;

for(i = 0; i < size; ++ i)
dxor ^= array[i];

if(dxor != 0)
{
j = whichbitone(dxor);
for(i = 0; i < size; ++ i)
{
if(isbitone(array[i],j) == 1)
num1 ^= array[i];
else
num2 ^= array[i];
}
/*得到第一个数*/
printf("first data is %d",num1);
printf("second data is %d",num2);
}
}

int main(int argc, char *argv[])
{
int array[10] = {1,2,3,4,7,2,3,1,4,9};
xortest(array,10);

return 0;
}

上面的代码基本上实现了上面的描述。

对于本题的另一个变换“数组中元素成对出现,但是存在三个不成对的元素,如何快速的找出这三个元素?”

这个题看起来和本题有一定的联系性,甚至我认为我们可以采用相同的方法找出三个值,但是后来发现这种方法存在一个问题,但是三个的情况要远远比两个的复杂,因为其中存在的可能性要多很多,不是不是属于这个元素就是另一个元素的问题,虽然这种解法可能导致问题产生,但是还是有可能解决的,除了当三个元素的异或结果为0,即x^y^z = 0时,这种方法是不成立的。
对于三个不同元素的找份,我认为主要是找到其中的一个元素,然后将这个元素移除,在进行上述的另外两个元素寻找。当然我们首先排除三个数据异或为零的特殊情况。具体的实现可以参考http://blog.csdn.net/zzran/article/details/8108787。

Copyright © 2017-2020 微波EDA网 版权所有

网站地图

Top