一.位运算
1.基本知识
(1).与 (&&)：两者皆是1即为1；其余为0；
或(||) ：一方为1皆为1；其余为0；
非 (!) ：！x,所得即为不是x；
异或(^) ：两者相同皆为0；不同为1；
(2).左移：1<<x （即为二进制中左移一位，其实就是扩大2倍）
右移：1>>x （即为二进制中右移一位，其实就是除以2）
(3).判断奇偶性
奇数的二进制最低位是1；
偶数的二进制最低位是0；
2.位运算典型的应用
（1）求模运算
例如：a乘b对p求模；a的b次方对p求模；等等
一般就是取模运算：a % p（或a mod p），表示a除以p的余数。比如给定一个正整数p，任意一个整数n，一定存在等式 ：n = kp + r ；其中 k、r 是整数，且 0 ≤ r < p，则称 k 为 n 除以 p 的商，r 为 n 除以 p 的余数。取模运算的规则如下：
1、(a + b) % p = (a % p + b % p) % p 。
2、(a - b) % p = (a % p - b % p) % p 。
3、(a * b) % p = (a % p * b % p) % p 。
4、a ^ b % p = ((a % p)^b) % p 。
一般就是会用快速幂=二分+拆分来减少计算， 一般快速幂 a的b次方，如3的7次方: 7=111（2） 3^7=3* 3^2 3^4.也就是ans=ansa，a每次在b右移一位后平方。对于a乘b，化为加法，3x7:=3+3x2+3x4，也就是ans=ans+a，a每次在b右移一位后乘以2.。
while(b)
{
if(b&1){
ans=ans*1lla%p;(有时范围大会转化为长整形long long ,会加个1ll)
}
a=a*1lla%p;
b>>=1;
}
``
while(b > 0){
if(b & 1){
ans = (ans + a) % p;
}
a = 2 * a % p;
b >>= 1;
}
二. 整数二分和浮点二分
1.二分一般就是用来查找的，整数二分用的比较多吧，有两种模板
（1）.找中间点
所以中间点应为mid=（l+r+1）/2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
（2）.中间点 mid=（l+r）/ 2
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
//(1)
```while(l<r)
{
int mid=(l+r+1)/2;
if(x<=a[mid])
{
l=mid;
}
else r=mid-1;
}
cout<<l<<endl;
return 0;
}
//(2)
```while(l<r)
{
int mid=(l+r)/2;
if(a[mid]>=x)
{
r=mid;
}
else l=mid+1;
}
cout<<r<<endl;
return 0;
}
``
2.浮点数二分
浮点数的模板比较简单，以一个题说明（数的三次方根）
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例：
输出样例：
说明： 当r-l足够小时，我们就假定已经找完， 用公式表示r-l<1e-6,此时有个精度问题如果要求保留6位小数则r-l<1e-8,总要比保留的小数多两位。
三.前缀和与差分
1.前缀和
一般就是一维前缀和二维前缀，就是求一列数的在哪个区间他们的和，也是有模板的。
一维的给定长度为n的序列a1,a2…an,则sum[i]=a1+…+ai=sum[i-1]+a[i]，求每个区间的和的话，
`
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
s[i] = s[i-1] + a[i];
while (m--)
{
int l,r;
cin>>l>>r;
cout<<s[r] - s[l-1]<<endl;
}
return 0;
}
// 有些是让每个数都加上c，以下是写的函数
void s(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}
//`二维前缀和就是如给定一个矩阵s[i][j]，sum[i][j]是矩阵的和。
```for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];
有些二维矩阵求区间的和
`ans=sum[x2][y2]-sum [x1-1][y2]-sum [x2][y1-1]+sum [x1-1][y1-1]；
