位运算/异或运算及其演变题目

学习笔记

异或运算 ^ ： 两个数按每个二进制位合并，相同为0，不同为1.

它有一些很神奇的性质：

  1. 0 ^ N = N
  2. N ^ N = 0
  3. 满足交换律和结合律 a ^ b = b ^ a , (a ^ b) ^ c = a ^(b ^ c) = 结果是一个固定的数

其实就是无进位相加

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

1
2
3
4
5
6
7
8
9
// 常规做法
int temp = a;
a = b;
b = temp
    
// 异或
a = a ^ b  // a = a^b  b=b
b = a ^ b  // b = a ^ b ^ b = a
a = a ^ b  // a = a ^ b ^ a = b

注意： a 和 b变量必须是独立的内存区域，不然计算会出错。

一个数组有一种数出现了奇数次，其他数都是偶数次，怎么打印这个数

[ a, b, a,c,c,d,d,d,d] 两个相同的数异或 = 0。

1
2
3
4
5
int result = 0;
for(int i = 0 ; i < arr.length - 1 ; i++) {
    result ^= arr[i]
}
return result;

小技巧: 怎么把一个int类型的数提取出最右侧的1来

比如 ： 0011011010101100 ， 得到结果0000000000000100

a & (-a) , -a = ~a + 1 , a取反加1就是负a

1
2
3
4
5
a      = 01101110010000
~a     = 10010001101111
~a + 1 = 10010001110000
------------------------
         00000000010000

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

解题思路分析

1
2
3
4
5
6
7
8
9
10
11
//假设一个数组arr[]： a和b出现了奇数次
a ^ b ^ ..... 异或所有 = a ^ b = eor
由于a != b , 所以a ^ b != 0
eor结果某个位置上一定为1 . 比如找eor最右侧的1 .  
    
//假设从右开始第三位为1，说明a的第三位和b的第三位一定不同
可以把arr[]所有的数分成两类，第一类是第三位是1的数，另一类是第三位是0的数
    
// 假设 a的第三位是1，b的第三位是0
eor` = 第三位是1的所有数异或 得到 a , 因为其他不是a的数一定会出现偶数次
b = eor ^ eor` = (a ^ b) ^ a  = b

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// arr中，有两种数，出现奇数次
public static void printOddTimesNum2(int[] arr) {
	int eor = 0;
	for (int i = 0; i < arr.length; i++) {
		eor ^= arr[i];
	}
	// a 和 b是两种数
	// eor != 0
	// eor最右侧的1，提取出来
	// eor :     00110010110111000
	// rightOne :00000000000001000
	int rightOne = eor & (-eor); // 提取出最右的1
	
	int onlyOne = 0; // eor'
	for (int i = 0 ; i < arr.length;i++) {
		//  arr[1] =  111100011110000
		// rightOne=  000000000010000
		if ((arr[i] & rightOne) != 0) {
			onlyOne ^= arr[i];
		}
	}
	System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

一个数组中有一种数出现了K次，其他数出现了M次，M > 1 ，K < M ，找打出现K次的数。