算法总结（二）

异或运算的骚操作

异或解释

  1. 异或运算，相同的值异或为0，不同的值异或为1
  2. 也可以理解为无进位的加法
  3. 异或运算满足交换律，结合律
  4. 一个数组中所有数的异或和 跟 某些数异或的结果 相当于 减去某些数的异或和

使用异或进行交换两个数

  1. a = a^b
  2. b = a^b (此时相当于a^b^b = a , 就让b等于a)
  3. a = a^b (此时相当于a^b^a = b , 就让a等于b)

局限性：注意这个交换不能对同一个地址的两个变量进行操作。因为第一步就会把他们都变为0

1
2
3
4
5
6
7
      int a = -2323;
int b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println(a);
System.out.println(b);

使用异或不用判断语句去判断两个数的大小

大体思路就是根据a-b的符号，来判断a和b的大小。
但是这样有溢出的风险（a-b会溢出）
优化思路：

  1. 获取a和b的符号
  2. 获取c=a-b的符号
  3. 综合判断
  4. 如果a,b符号相同，则不可能溢出，直接根据c的符号来判断大小
  5. 如果a,b符号不同，则a-b可能会溢出，判断a的符号 如果a是非负的，就可以直接返回a更大
  6. 除了以上两种情况，其余情况都返回b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
   // 必须保证n一定是0或者1
// 0变1，1变0
public static int flip(int n) {
	return n ^ 1;
}

// 非负数返回1
// 负数返回0
public static int sign(int n) {
	return flip(n >>> 31);
}

// 有溢出风险的实现
public static int getMax1(int a, int b) {
	int c = a - b;
	// c非负，returnA -> 1
	// c非负，returnB -> 0
	// c负数，returnA -> 0
	// c负数，returnB -> 1
	int returnA = sign(c);
	int returnB = flip(returnA);
	return a * returnA + b * returnB;
}

// 没有任何问题的实现
public static int getMax2(int a, int b) {
	// c可能是溢出的
	int c = a - b;
	// a的符号
	int sa = sign(a);
	// b的符号
	int sb = sign(b);
	// c的符号
	int sc = sign(c);
	// 判断A和B，符号是不是不一样，如果不一样diffAB=1，如果一样diffAB=0
	int diffAB = sa ^ sb;
	// 判断A和B，符号是不是一样，如果一样sameAB=1，如果不一样sameAB=0
	int sameAB = flip(diffAB);
	int returnA = diffAB * sa + sameAB * sc;
	int returnB = flip(returnA);
	return a * returnA + b * returnB;
}

使用异或去返回出现了奇数次的数（其余数都出现了偶数次）

思路很简单，就是把所有的数异或一遍，最后剩下的数就是出现了奇数次的数。
因为异或满足交换律。凡是出现偶数次的数，异或结果都为0，最后结果就是奇数次的数^0 = 奇数次的数

1
2
3
4
5
6
7
   public static int singleNumber(int[] nums) {
	int eor = 0;
	for (int num : nums) {
		eor ^= num;
	}
	return eor;
}

使用异或去返回两个出现奇数次的数（其余数都出现了偶数次）

思路：(假设那两个数为a和b)

  1. 先将数组中所有数异或一遍，得到一个数xor1=a^b
  2. 找到xor1最右边的1，即xor1 & (-xor1) (解释：xor1 & (-xor1)可以获取xor1最右边的1。并且这个1就是a跟b肯定不一样的数位（当然不只这一个，但是只需要这一个我们就可以区分它们了）)
  3. 将数组中所有数分为两组，一组是xor1最右边的1为1的数，一组是xor1最右边的1为0的数 （a,b肯定在不同的组中）
  4. 对其中一组数异或，得到XOR2 (XOR可能是a也有可能是b) （每组还是满足除了a,b之外所有数出现次数都是偶数）
  5. 讲XOR2与XOR1异或，得到另一个数 （XOR2^XOR1=a^b^b=a (假设XOR是b)）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
       public static int[] singleNumber(int[] nums) {
	int eor1 = 0;
	for (int num : nums) {
		// nums中有2种数a、b出现了奇数次，其他的数都出现了偶数次
		eor1 ^= num;
	}
	// eor1 : a ^ b
	// Brian Kernighan算法
	// 提取出二进制里最右侧的1
	int rightOne = eor1 & (-eor1);
	int eor2 = 0;
	for (int num : nums) {
		if ((num & rightOne) == 0) {
			eor2 ^= num;
		}
	}
	return new int[] { eor2, eor1 ^ eor2 };
}

其他位运算的骚操作

判断一个数是不是2的幂

原理： 如果是2的幂，那么二进制数只有一位为1，其他为0 。这时候我们用a&-a 拿到到的数，就是a最右边的1。然后判断a是不是等于a&-a 等于的话，那么a就是2的幂。

1
2
3
public static boolean isPowerOfTwo(int a) {
	return a > 0 && a==(a&-a);
}

判断一个数是不是三的幂

1
2
3
4
5
6
7
8
   // 如果一个数字是3的某次幂，那么这个数一定只含有3这个质数因子
// 1162261467是int型范围内，最大的3的幂，它是3的19次方
// 这个1162261467只含有3这个质数因子，如果n也是只含有3这个质数因子，那么
// 1162261467 % n == 0
// 反之如果1162261467 % n != 0 说明n一定含有其他因子
public static boolean isPowerOfThree(int n) {
	return n > 0 && 1162261467 % n == 0;
}

返回大于等于n的最小的2某次方

先对n-1 然后把n最左边的1一直让右边全变为1.最后的答案就是n+1 (00111111 -> 01000000)

1
2
3
4
5
6
7
8
9
10
11
12
public static final int near2power(int n) {
	if (n <= 0) {
		return 1;
	}
	n--;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return n + 1;
}

此区间内所有数字 & 的结果(连续)

形如 0111001000 如果此时还存在一个比自己还小的数，那么我最右边的1肯定会被与运算变成0.直到最小的数都大于我，我的最右侧的1才能保留下来。

1
2
3
4
5
6
public static int rangeBitwiseAnd(int left, int right) {
	while (left < right) {
		right -= right & -right;
	}
	return right;
}

统计一个数的二进制中1的个数

具体思路参考 【算法讲解031【必备】位运算的骚操作】https://www.bilibili.com/video/BV1ch4y1Q7vd?vd_source=c6cdeb45f015e4ab4447a6c61482633a

1
2
3
4
5
6
7
8
public static int cntOnes(int n) {
	n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
	n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
	n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
	n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
	n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
	return n;
}

位运算实现加减乘除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public static int MIN = Integer.MIN_VALUE;

public static int divide(int a, int b) {
	if (a == MIN && b == MIN) {
		// a和b都是整数最小
		return 1;
	}
	if (a != MIN && b != MIN) {
		// a和b都不是整数最小，那么正常去除
		return div(a, b);
	}
	if (b == MIN) {
		// a不是整数最小，b是整数最小
		return 0;
	}
	// a是整数最小，b是-1，返回整数最大，因为题目里明确这么说了
	if (b == neg(1)) {
		return Integer.MAX_VALUE;
	}
	// a是整数最小，b不是整数最小，b也不是-1
	a = add(a, b > 0 ? b : neg(b));
	int ans = div(a, b);
	int offset = b > 0 ? neg(1) : 1;
	return add(ans, offset);
}

// 必须保证a和b都不是整数最小值，返回a除以b的结果
public static int div(int a, int b) {
	int x = a < 0 ? neg(a) : a;
	int y = b < 0 ? neg(b) : b;
	int ans = 0;
	for (int i = 30; i >= 0; i = minus(i, 1)) {
		if ((x >> i) >= y) {
			ans |= (1 << i);
			x = minus(x, y << i);
		}
	}
	return a < 0 ^ b < 0 ? neg(ans) : ans;
}

public static int add(int a, int b) {
	int ans = a;
	while (b != 0) {
		// ans : a和b无进位相加的结果
		ans = a ^ b;
		// b : a和b相加时的进位信息
		b = (a & b) << 1;
		a = ans;
	}
	return ans;
}

public static int minus(int a, int b) {
	return add(a, neg(b));
}

public static int neg(int n) {
	return add(~n, 1);
}

// 这种乘法后面有大用处，尤其是求(a的b次方 % m)的结果，也叫龟速乘
public static int multiply(int a, int b) {
	int ans = 0;
	while (b != 0) {
		if ((b & 1) != 0) {
			// 考察b当前最右的状态！
			ans = add(ans, a);
		}
		a <<= 1;
		b >>>= 1;
	}
	return ans;
}