位运算之异或问题
异或运算的基础
基本运算法则部分
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