2、异或运算的性质与扩展

异或又被叫做：模二运算（相加不进位）

异或的特性
a ^ a = 0
a ^ 0 = a
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

通过一个demo熟悉上面的特性

public void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
//arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j]
arr[j] = arr[i] ^ arr[j];
//arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j] ^ arr[j] = arr[i]
arr[i] = arr[i] ^ arr[j];
//arr[i] = arr[i] ^ arr[j] ^ arr[i] = arr[j];
arr[j] = arr[i]
}

上面的例子比平时交换两个值的方式要快，但是存在一个缺点：两个值不能是同一个地址

若arr[i] == arr[j],第一步 arr[i] = arr[i] ^ arr[j] = 0

通过上面的介绍，我们熟悉了异或运算的特性，下面将使用异或操作的特性解决两道算法题：

1、一个数组中有一个数出现了奇数次，其他数都出现了偶数次，请找出出现了奇数次的这个数

思路：定义一个常量a = 0,让a和所有元素进行异或操作，由于相同的元素会相互抵消，最后剩下的元素就是出现了奇数次的那个值

public int oddNumber(int[] arr) {
int a = 0;
for(int i=0; i < arr.length; i++) {
a = a ^ arr[i];
}
return a;
}

2、一个数组中有2个数出现了奇数次，其他数都出现了偶数次，请找出这两个出现了奇数次的数值

public int[] evenNumber(int[] arr) {
//假设两个奇数分别为x和y
//求出a = x ^ y;
int a = 0;
for(int i=0; i < arr.length; i++) {
a = a ^ arr[i];
}
//求出a的二进制中 最右边的1 (求出任何一位的1都可以)
int temp = a & (~a + 1);
//求出b = x或者b = y
int b = 0;
for(int i=0; i < arr.length; i++) {
if((temp & arr[i]) == 0) {
b = b ^ arr[i];
}
}
//此时 a = x ^ y;
b = x
int[] result = new int[2];
result[0] = b;
//x
result[1] = a ^ b; //x ^ y ^ x = y
return result;
}

最后

以上就是追寻便当为你收集整理的算法基础入门 - 2、异或运算的性质与扩展2、异或运算的性质与扩展的全部内容，希望文章能够帮你解决算法基础入门 - 2、异或运算的性质与扩展2、异或运算的性质与扩展所遇到的程序开发问题。

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