0%

位运算

位运算

补码

  • 有符号和无符号

  • memset

  • 0x3f=0011 1111

  • 0xff=1111 1111

    移位运算

  • 左移: 二进制下数字左移,右填0,高位弃 $1<<n=2^n$

  • 算术右移: 在补码下右移,高位按符号位填,低位舍,相当于除以2,向下取整

  • 逻辑右移: 高位填0,使用逻辑或算术根据编译器来,但新的一般算术.

快速幂

根据快速幂,将$a^b$拆分为$a^{c_{k-1}2^{k-1}}a^{c_02^0}$

此时有$k=[log_2(b+1)]$(向上取整),即至多k次求出每项(使用递推),每次系数(位)是1时乘一次. 复杂度为$O(log_2b)$

1
2
3
4
5
6
7
8
9
10
int fp(int a ,int b,int p)//(a^b)mod p
{
int ans=1%p;
while(b){
if(b&1)ans=(long long)ans*a%p;
a=(long long )a*a%p;//平方即幂次乘2
b>>=1;
}
return ans;
}

其中的longlong 转换是为了有一个”高级”类型,最后取模后隐式转换回int类型

64位整型乘法

  • 求$(a*b)mod p$,其中ab均为64位整型(<1e18)

注意此时直接乘会把ll给爆了,需要128整型,但是可以用别的方法

拆分法

仿照快速幂,显然我们可以将b拆分为多个$C_{k}2^{k}$利用一个不断乘2的变量,递推,每当系数为1,乘在答案上.最多次数和快速幂相同.

1
2
3
4
5
6
7
8
9
10
11
long long mul(long long a,long long b, long long p){
long long ans=0;
while(b){
if(b&1){
ans=(ans+a)%p;
}
a=(a*2)%p;
b>>=1;
}
return ans;
}

利用取模计算公式

提及大位数乘法,显然可以用浮点,但是long double在十进制下的精度也只有1e18左右,显然不能用但是有一个很妙的转换

  • 有$abmodp= ab-\lfloor ab/p \rfloorp $
  • 对于$\lfloor a*b/p\rfloor$,本来就是要向下取整的,而浮点数失去精度时,会丢失低位,刚刚好(注意数据范围和long double精度)
  • 计算出后式后,对于$ab-\lfloor ab/p \rfloor*p $,虽然两者都很大,但是其差必然小于p,考虑到longlong溢出是高位损失,又是刚刚好.
1
2
3
4
5
6
7
8
long long mul(long long a,long long b,long long p){
long long tmp=(long double)a*b/p;//向下取整
//只要转换就行了
long long tmp2=a*b-tmp*p;
if(tmp2<0) tmp2+=p;
else if(ans>=p) tmp2-=p;
return tmp2;
}

二进制压缩状态

即将长度为m的bool数组,用m位二进制整型表示和储存

操作 运算
取出n在二进制下第k位 (n>>k)&1
取出n在二进制下的0~k-1位(后k位) n&((1<<k)-1)
对n在二进制下的第k位取反 n xor (1<<k)
对n在二进制下的第k位写1 n | (1<<k)
对n在二进制下的第k位写0 n & (~(1<<k))

对于m很小时,直接用一个整型变量就可以储存,大数据时,可以用一个整型数组,或者直接用stl提供的bitset

最短hamilton路径

1
对于 一张n<=20个节点的带权无向图,从0标号,求起点0到终点n-1的最短hamilton路径(hamilton路径: 从0到n-1不重不漏经过每个点)

使用BF算法,枚举全部排列,时间复杂度为$O(nn!)$,使用二进制状压dp可以得到$O(n^22^n)$.

定义$F[i,j]$为$i$状态,目前在$j$处的值,全部初始化为inf

则有转移方程$F[i,j]=min(F[i XOR (1<<j),k]+weight[k,j])$

从i追溯回去(判断i状态时候满足访问过j的条件)

1
2
3
4
5
6
7
8
9
10
11
12
13
int f[1<<20][20];
int hamilton(int n,int weight[20][20]){
memset(f,0x3f,sizeof f);
f[1][0]=0;
for(int i=1;i<1<<n;i++){
for(int j=0;j<n;j++)if(i>>j&1)
for(int k=0;k<n;k++)
if((i^1<<j)>>k&1)
f[i][j]=min(f[i][j],
f[i^1<<j][k]+weight[k]);
}
return f[(1<<n)-1][n-1];
}

成对变换

  • 邻接表的重要工具
  • 有规律:
    • n为偶数时,nxor1=n+1;
    • n为奇数时,nxor1=n-1;
  • 故通过xor1操作,01,23,45….可以成对表示

lowbit运算

lowbit(n)定义为非负整数n在二进制表示下”最低位的1和其后所有的0”构成的数

求法: 对n取反再加一,然后和n按位与

注意,n+1在补码表示下就是-n (n=-n-1)

1
2
3
int lowbit(int n){
return n&(-n);
}

配合hash 求一个整数二进制下所有是0的位

每一次lowbit都可以求出最低位的1,则只要不断lowbit 然后减去这个数,然后继续lowbit.

每次求出的数,有$2^k=n$即求对数即为位数,由于cmath库中提供的log是浮点,且慢 ,所以一般用hash的方法直接预处理出一个对数表

简单法但复杂

数据较小时,比如2的20次方,我们直接开一个大数组,并使得其中2的整数次方位下标的值为其指数,显然,只有非常少($2^{20}$中只有20位)位数被利用

高效的方式

有一个数学技巧: 在$-1<k<36$时,$2^kmod37$不会重复,并且其值取遍1-36,那么显然,我们只开一个37大的数组,将0-35次幂的值写入对应下标即可