位运算之异或问题

位运算之异或问题

异或运算的基础

基本运算法则部分

	a ^ b = b ^ a
	a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
	d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
	a ^ b ^ a = b
	a^0=a
	a^a=0

异或运算之只有一个出现奇数次的值

原题:假定有一个数组里面有整数, 但是其中只有一个数只出现了奇数次,其余的每个数都出现了偶数次,求出现奇数次的数是那个数。

解题思路:
由于我们知道假如两个数相同的话,他们之间进行异或运算会得到结果为0,即a^a=0,那么我们就可以先将所有的数用一个数组保存起来,再利用循环将数组里面的所有数给异或就能得到一个结果,而这个结果的值即我们要求的值。

话不多说,上代码!
        int arr[]={1,2,3,4,5,6,7,10,8,9,9,8,7,6,1,5,4,3,2};//随机定义一个数组
        int e=0;//初始化一个值,用于保存最后的结果
        for (int i=0;i<arr.length;i++){
            e^=arr[i];
        }
        System.out.println("最后得到的那一个出现奇数次的值为"+e);
运行结果
	最后得到的那一个出现奇数次的值为10

异或运算之有两个出现奇数次的值

原题:同样出现一个数组,但是这一次的话,我们已知这个数组里面有两个出现奇数次的值,其他的值均出现偶数次,求出这两个数的值;

解题思路:
我们看到这个题的第一思路肯定是我们先将所有偶数次的值先去掉,那么这个我们也可以通过异或运算得到;(假设我们这两个奇数次的值为a和b),我们通过运算后将会得到一个a^b的值。但是我们现在仅仅知道的是a ^ b的值,并不知道他们具体的值,那么我们怎么办呢?此时到达了该题的关键点。我们既然知道两个相同的数异或结果为0,那么我们还有一个呀,那就是相同的数得到的异或结果也是一样呀,我们假设e=a^b,那么用e去和每一个数异或,得到的值在用一个新的数组存起来,然后将得到的数组,相同的结果的值给置空,最后不为空的即是我们剩下的值了呀;

话不多说,上代码!
        int[] arr ={1,2,3,4,5,6,6,5,4,3};
        int e=0;
        int[] arr1=new int[arr.length];
        for(int i=0;i<arr.length;i++){
            e=arr[i]^e;//求出两个特殊值的异或值
        }
        for (int i=0;i<arr.length;i++){
            arr1[i]=e^arr[i];//将每个数都和e抑或并逐个保存下来
        }
        for(int i =0;i<arr1.length;i++){
            for(int j =1;j<arr.length;j++){
                if(j!=i){
                    if(arr1[i]==arr1[j]){//将相同的异或值提取出来置0
                        arr[i]=0;
                        arr[j]=0;
                    }
                }
            }
        }
        System.out.print("最终得到的两个值即:");
        for(int i=0;i< arr1.length;i++){
            if(arr[i]!=0){//最后不为0的即我们最后剩下的两个值
                System.out.print(arr1[i]+"\t");
            }
        }

运行结果
最终得到的两个值即:2	1
注:如果有什么不对的地方请联系我,谢谢您的阅读!
上一篇:《C语言复习》-数组


下一篇:MySQL索引的创建,查看,删除,修改操作详解(上)