一些有用小操作

mid溢出

在使用二分法的时候经常会用到一行代码:

1	mid = (left + right) / 2;

很正常的思维，mid就是left和right的中间值嘛。

但是当right为INT_MAX也就是int上限的时候，left+right会导致mid溢出。

如果这样写就可以避免这个溢出了。

1	mid = left + ((right - left) >> 1); // >> 1 表示除以2

要养成这样写mid的习惯。

小时候看一本算法书当中依稀记得mid就是这样的，当时无知的自己还嘲笑作者喜欢装逼，又加法又减法又位运算的。

乘法取模

在计算一些大数的时候，往往题目会要求对一个较大的质数取模。

例如

(这道题每步取模就够用了)

快速幂

#define MOD 200907

long long myPow(int x, int n)
{
	long long ans = 1;
	while (n) {
		if (n & 1) ans = (ans * x) % MOD;  //遇到1了，把当前结果乘进ans里
		x = (x * x) % MOD;
		n >>= 1;  //n的二进制右移一位
	}
	return ans % MOD;
}

但这里有一个问题，如果中途ans*x这步就直接导致溢出了怎么办？

乘法的原理就是不断地加，我们可以用类似于快速幂的方法写一个快速乘（虽然并不快速），不过目的是保证在乘法过程中每步取模，不会出现溢出。

#define MOD 200907

int quickAdd(int a, int b) {
	int res = 0;
	while (b) {
		if (b & 1) {
			res = (res + a) % MOD;
		}
		a = (a + a) % MOD;
		b >>= 1;
	}
	return res % MOD;
}

后续可能还会更新…