001.异或运算

大家好，欢迎来到IT知识分享网。

认识异或运算

异或运算：相同为0，不同为1

同或运算：相同为1，不同为0

能长时间记住的概率接近0%

所以，异或运算就记成无进位相加！

异或运算的性质

1）0 ^ N == N N ^ N == 0

2）异或运算满足交换律和结合律

​ 相当于几个数在一起进行异或运算 不论数的顺序是否相同 得到的结果都是一样的

如下例子：

上面的表格可以看出来，无论你的顺序是 a ^ b ^ c 还是 b ^ c ^ a 还是 b ^ a ^ c 等 得到的结果都是一样的，因为每一个位置上的结果与 a b c 对应位置的值有关，与其它位置无关。

上面的两个性质用无进位相加来理解就非常的容易

题目一 如何不用额外变量交换两个数

这种方式的前提是两个变量指向的内存不同才可以进行交换，否则计算处理等于0

int a = 甲 ， int b = 乙；

a = a ^ b;

b = a ^ b;

a = a ^ b ;

最后的结果就是 a = 乙，b = 甲

证明：

int a = 甲 ， int b = 乙；

a = a ^ b = 甲 ^ 乙

b = a ^ b = (a ^ b) ^ b = a ^ b ^ b = 甲 ^ 乙 ^ 乙 = 甲 ^ 0 = 甲

a = a ^ b = (a ^ b) ^ 甲 = 甲 ^ 乙 ^ 甲 = 乙

所以 a = 乙，b = 甲

public static void main(String[] args) { 
    int a = 300; int b = 345; System.out.println("---交换之前---"); System.out.println("a = " + a); System.out.println("b = " + b); a = a ^ b; b = a ^ b; a = a ^ b; System.out.println("---交换之后---"); System.out.println("a = " + a); System.out.println("b = " + b); // 数组里面的值进行交换 int[] arr = { 
   3,1,100}; System.out.println("---交换之前---"); System.out.println("arr[0] = " + arr[0]); System.out.println("arr[2] = " + arr[2]); swap(arr, 0 , 2); System.out.println("---交换之后---"); System.out.println("arr[0] = " + arr[0]); System.out.println("arr[2] = " + arr[2]); } public static void swap(int[] arr, int i , int j) { 
    arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } 运行结果如下： ---交换之前--- a = 300 b = 345 ---交换之后--- a = 345 b = 300 ---交换之前--- arr[0] = 3 arr[2] = 100 ---交换之后--- arr[0] = 100 arr[2] = 3 

特别注意：

这种方式的前提是两个变量指向的内存不同才可以进行交换，否则计算处理等于0

例如：

public static void main(String[] args) { 
    int[] arr = { 
   3,1,100}; System.out.println("---交换之前---"); System.out.println("arr[0] = " + arr[0]); System.out.println("arr[2] = " + arr[2]); swap(arr, 2 , 2); System.out.println("---交换之后---"); System.out.println("arr[2] = " + arr[2]); System.out.println("arr[2] = " + arr[2]); } public static void swap(int[] arr, int i , int j) { 
    arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } 执行结果： ---交换之前--- arr[0] = 3 arr[2] = 100 ---交换之后--- arr[2] = 0 arr[2] = 0 

题目二 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数。

所有的数都异或运算起来，因为异或运算的结果与数的位置无关，并且其他数出现的次数都是偶数次，只有一种数是奇数次，所以所有的数异或运算之后就是该种数

// arr中，只有一种数，出现奇数次 public static void printOddTimesNum1(int[] arr){ 
    int eor = 0; for (int i = 0; i < arr.length; i++) { 
    eor ^= arr[i]; } System.out.println(eor); } 

题目三 怎么把一个int类型的数，提取出最右侧的1来

例子：

0000

00000000001000

0000

00000000000010

n & ((~n) + 1) n 与 （n取反后再加1）

例如

n = 0 0 0 0 1 1 1 0 1 0 1 0 0 0

~n = 1 1 1 1 0 0 0 1 0 1 0 1 1 1

~n + 1 = 1 1 1 1 0 0 0 1 0 1 1 0 0 0

n & (~n + 1) = 00000000001000

题目四 一个数组中有两种数出现了奇数次，其他数都是出现了偶数次，怎么找到并打印这两种数。

首先进行分析

假设两种出现次数为奇数次的数分别是 a 或 b

那么数组中的数全部进行异或运算之后的结果就是 eor = a ^ b

eor 的结果肯定是不为 0 的（如果为0 表示 a == b）

那么 eor 不为0 的位置 就是 a 和 b 数的不同的位置了。

这里假设 eor = 0

如果为1就代表 a 和 b 数不相同的 位置了

选择其中的一个位置就可以进行区分

这里选择最后一个为1 的位置 0000000100

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZGqIraid-40)(imgs/image-.png)]

然后在进行异或运算之前先判断一下这个位置不等于0的数

如果不为0然后进行异或运算之后的结果就是b

最后进行 eor ^ b = a ^ b ^ b = a

代码如下：

// arr 中，有两种数，出现奇数次 public static void printOddTimesNum2(int[] arr){ 
    int eor= 0; for (int i = 0; i < arr.length; i++) { 
    eor ^= arr[i]; } // eor = a ^ b // eor != 0 // eor 必然有一个位置上是1 int rightOne = eor & (~eor + 1); // 提取出最右的 1 int onlyOne = 0; //eor for (int i = 0; i < arr.length ; i++) { 
    if ((rightOne & arr[i]) != 0) { 
    onlyOne ^= arr[i]; } } System.out.println(onlyOne + " " + (onlyOne ^ eor)); } 

题目五 计算出一个int类型的数中的二进制数为1的个数

该题目就是先找到最右边不为0的值

然后将count++

紧接着就进行异或运算将该位置上的1去掉，然后进行下一次的循环，直到将N赋值为0后就跳出循环，最后得到的结果就是 1 的个数。

public static int bit1Counts(int N){ 
    int count = 0; while (N != 0) { 
    int rightOne = N ^ (~N + 1); count++; N ^= rightOne; } return count; }