C++位运算及其相关应用快速幂及最短Hamilton路径代码模板

今天药忘吃喽~ 2023-07-24 02:48 26阅读 0赞

### 文章目录 ###

*   *   *  基础知识
         *  位运算的应用
         *   *   *  1.快速幂模板
                 *  2.大数相乘模板
                 *  3.最短Hamilton路径模板
                 *  4.异或求配偶数
                 *  5.lowbit运算

### 基础知识 ###

与：&，同为1时为1，否则为0  
或：|，有1为1，没1为0  
非：!，1为0，0为1  
异或：^，相同为0，不同为1，类似不进位加法  
反码：按位取反  
补码：反码加1  
左移位：整体向左移n位，右边补0，相当于乘了2n  
右移位：整体向右移n位，左边补符号位，相当于除以2n

--------------------

### 位运算的应用 ###

##### 1.快速幂模板 #####

若计算a的n次幂是一般要循环n次，让n个a相乘，时间复杂度为o(n)，若n很大时如n = 109 时要循环 109次。为了减少循环，我们用大数相乘得答案。举个例子：如计算37时，我们直接计算31 \* 32 \* 3 4，这样只需要循环三次即可。

#include<iostream>
    
    using namespace std;
    
    int main()
    { 
    	int a,n,ans = 1;	//ans为答案
    	cin >> a >> n;
    	while(n)	//直到n移完所有位时退出循环
    	{ 
    		if(n & 1)	//如果ans的二进制最后一位是1，ans乘上a
    			ans = ans * a;
    		a = a * a;	//每移位一次，a平方一次
    		n >>= 1;	//n右移1位
    	}
    
    	return 0;
    }

37 = 31 \* (31)2 \* ((3 1)2)2，所以每移位一次，a平方一次，对n进行二进制分解，若n的最后一位为1，则乘上此时的a。

##### 2.大数相乘模板 #####

若计算a乘b对p取模的值（1 < a,b,p < 1018），由于a，b的乘积超出了int型范围，所以我们无法直接a*b，我们可以用高精度模拟乘法计算，但是我们可以利用位运算来简化操作，和快速幂的思想相同。  
在计算a*b时，其实就是b个a相加，所以我们可以用a+2a+4a+…+2ka，使得1+2+4+…+2k = b，即可计算出a\*b，所以我们只需要对b进行二进制分解，向右移位进行判断。

#include<iostream>
    
    using namespace std;
    typedef long long LL;
    
    int main()
    { 
    	LL a,b,p,ans = 0;
    	cin >> a >> b >> p;
    	while(b)
    	{ 
    		if(b & 1)	//若b的二进制最后一位为1，ans加上a
    			ans = (ans + a) % p;
    		a = 2 * a % p;	//a每次乘二，这里先取模和最后模的答案一样，先取模可减少运算量
    		b >>= 1;	//b右移一位
    	}
    	cout << ans;
    
    	 return 0;
    }

##### 3.最短Hamilton路径模板 #####

给定一张n个点的带权无向图，n个点编号 0 ~ n - 1，求起点0到终点 n - 1的最短Hamilton路径。Hamilton路径是指从 0 到 n - 1每个点都要不重不漏的经过一次。（n <= 20）

对于这个问题，我们要确定最后一个点为n-1，并且每个点都走过，这里不要求每个点的具体顺序，只要确定每个点都走过一遍就行。  
所以这是一个状态压缩dp问题，需要两个状态：1.经过了哪些点。2.最后的终点是哪个点。  
状态表示：用二维数组f\[i\]\[j\]表示，i表示状态1，j表示状态2 。对于 i 有2n种情况，若n = 20时每个点经历过与没经历过有220种情况，所以我们在这就用位运算来表示，用20位的二进制数来表示每个点的遍历情况000……000，若该点经历过了就为1，若未经过就为0 。例如只遍历过了0、1、4的点，则i为00…010011 。**所以f\[i\]\[j\]就是遍历过i状态的点且终点为j点的最短路径。**  
状态计算：f\[i\]\[j\]需要从已遍历过的k点转移过来，就是**f\[i\]\[j\] = f\[ i 状态去掉点 j 的状态\]\[k\] + weight\[k\]\[j\]**，就是从状态 i 去掉点 j ，即没遍历到j点的状态且终点为k的最小值加上k点到j点的距离。这里要遍历所有走过的点求出最小值点k点。

#include<iostream>
    #include<cstring>
    
    using namespace std;
    const int N = 21,M = 1 << 20;
    int weight[N][N],f[M][N];
    
    int main()
    { 
    	int n;
    	cin >> n;
    	for(int i = 0;i < n;i++)
    		for(int j = 0;j < n;j++)
    			cin >> weight[i][j];
    	
    	memset(f,0x3f,sizeof f);
    	f[1][0] = 0;
    	for(int i = 0;i < 1 << n;i++)	//循环2^n种情况
    	{ 
    		for(int j = 0;j < n;j++)	//循环终点
    		{ 
    			if(i >> j & 1)	//判断f[i][j]的合法性，i状态必须包含j点才能使j点作为终点，所以判断i的第j位是否是1
    			{ 
    				for(int k = 0;k < n;k++)	//k循环一遍所有点作为倒数第二点转移过来
    				{ 
    					if(i - (1 << j) >> k & 1)	//判断合法性，i去掉j点的状态是否包含k点，即i的第j位改为0再判断此时的第k位是否为1
    						f[i][j] = min(f[i][j],f[i-(1 << j)][k] + weight[k][j]);
    				}
    			}
    		}
    	}
    	
    	cout << f[(1 << n)-1][n-1];	//根据状态表示，i的所有位均为1且终点j为n-1点的值为所求答案
    	
    	return 0;
    }

##### 4.异或求配偶数 #####

0，1  
2，3  
4，5  
这些均为配偶数  
0的配偶数为 0^1 = 1，1的配偶数为 1^1 = 0。  
2的配偶数为 2^1 = 3，3的配偶数为 3^1 = 2

某数异或1得到其配偶数  
求正向边的反向边e\[index\]，e\[index^1\]  
这在网络流等中会广泛使用

##### 5.lowbit运算 #####

意思是求出某二进制数的最后一位1的数是多少 计算有多少位1  
例如：  
lowbit（00011001000）= 1000  
lowbit（011110010100）= 100  
做法：

int lowbit(n)
    { 
    	return (-n) & n;
    }

这在树状数组中会广泛使用