【基本技巧】位运算-移位运算

1.左移

高位越界抛弃,低位补0。

1 << n = 2^{n};n << 1 = 2 \times n

2.算术右移

高位以符号位填充,低位越界抛弃

n >> 1 = \left \lfloor \frac{n}{2} \right \rfloor

3.逻辑右移

即Java中的无符号右移,高位补0,低位越界抛弃

但C++标准中并没有定义实现。

【例题】\large a^{b}\mod\ p,相关题目:POJ 1995, Luogu 1226

a^{b}\mod\ p;1 \leq a,b,p \leq 10^{9}

令 \large b 二进制有 \large k 位,第 \large i \large (o \leq i < k)位数字为\large c_{i},则:

\large b=\sum_{i=0}^{k-1}c_{i}\times 2^{i},则:

\large a^{b}=\prod_{i=0}^{k-1}a^{c_{i}\times 2^{i}},又:k=\left \lceil \log_{2}b+1 \right \rceil,且:a^{2^{i}}=a^{(2^{i-1})^{2}}

则可通过 \large k 次递推求出每个乘项,\large c_{i} = 1时累乘, \large b  & 1可得b在二进制下的最低位,而 \large b  >> 1可以舍去最低位。

typedef long long int64;

int binaryPow(int a,int b,int p){
	int ans = 1 % p;
	for(;b; b >>= 1){
		if(b & 1){
			ans = (int64) ans * a % p;
		}
		a = (int64) a * a % p;
	}
	return ans;                            
}

【例题】64位整数乘法

a \times b \mod\ p;1 \leq a,b,p \leq 10^{18}

同上题,\large b=\sum_{i=0}^{k-1}c_{i}\times 2^{i},则:

a\times b=\sum_{i=0}^{k-1}a\times c_{i}\times2^{i},又a\times 2^{i}=a\times 2^{i-1}\times 2,递推时不爆int64

typedef long long int64;

int64 time(int64 a,int64 b,int64 p){
	int64 ans = 0;
	for(;b;b >>= 1){
		if(b & 1){
			ans = (ans + a) % p;
		}
		a = a * 2 % p;
	}
	return ans;
}