一、位运算是什么？

位运算有以下几种分类：
与 x&y
或 x|y
非 !x
异或 x^y
int 是32位机器数
1:0000000…01
2:0000000…10
3:0000000…11
补码：类似于补数，例如4的补数是6,23的补数是77.两个相加得到一个整数。
1+x=000000
x=000000-1
1+1111…1111=000000…000所以计算机里面用1111…1111表示-1
x加上一个数是000000…0000
这个数就等于~x（x取反）+1。所以x的补码就用x取反+1。
用加法实现减法：-n=~n+1；
初始化数组为正无穷的方法：

memset(f,0x3f,sizeof f);
0x3f3f3f * 2 < 0xffffffff;

二、例题

1.a^b

题目描述：
求a 的b次方对p取模的值。
输入格式
三个整数a，b，p，在同一行用空格隔开
输出格式
输出一个整数，表示a^bmodp的值
数据范围
1<=a,b,p,<=10^9
输入样例
3 2 7
输出样例
2
经典做法是用快速幂
以下是快速幂的模板

int qmi(int m, int k, int p)
{
int res = 1, t = m;
while (k)
{
if (k & 1)res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}

本题代码

#include <iostream>
using namespace std;
int main()
{
int a, b, p;
cin >> a >> b >> p;
int res = 1;
while (b) {
if (b % 1)res = res * 1ll * a % p;
a = a * 1ll * a % p;
b >>= 1;
}
cout << res << endl;
return 0;
}

在运行过程中，题目样例输入是可以通过的，但是当输入数据变为123456789 0 1时，会产生错误。因为此时当b=0时，while(b)直接跳出循环。只需在int res=1时改为int res=1%p
即

#include <iostream>
using namespace std;
int main()
{
int a, b, p;
cin >> a >> b >> p;
int res = 1%p;
while (b) {
if (b % 1)res = res * 1ll * a % p;
a = a * 1ll * a % p;
b >>= 1;
}
cout << res << endl;
return 0;
}

2.64位数乘运算

题目描述：
求a乘b对p取模的值。
1 <= a, b, p <= 10 ^ 18
输入格式
第一行输入整数a，第二行…
输出格式
输出一个整数表示a乘b对p取模的值。
输入样例
3
4
5
输出样例
2

注意问题：两个10 ^ 18相乘会溢出，但两个10 ^ 18相加不会溢出，所以解决办法就是把乘法变成加法
a * b->a + a + a + a + … + a
a * 1 = a
a * 2 = 2a
a * 4 = 4a
a * 8 = 8a
…
a * (2 ^ k) = 2 ^ k * a
本题代码

#include<iostream>
using namespace std;
typedef unsigned long long ULL;
int main()
{
ULL a, b, p;
cin >> a >> b >> p;
ULL res = 0;
while (b) {
if (b & 1)res = (res + a) % p;
b >>= 1;
a = a * 2 % p;
}
cout << res << endl;
return 0;
}

3.最短Hamiton路径

题目描述：

题目大意：给定一个 N 个点的无向图，点有点权，
求从 0 号点走到 N - 1 号点的最短哈密顿路径是多少。
注意两点问题：
1.那些点被用过
2.目前停在了哪个点上

f[state][j] = f[state_k][k] + weight[k][j];
state_k = state去掉j之后的集合

本题代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20, M - 1 << 20;
int n;
int f[M][N], weight[N][N];
int main()
{
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++)
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][j]);
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}

最后

以上就是冷艳心锁为你收集整理的位运算一、位运算是什么？二、例题的全部内容，希望文章能够帮你解决位运算一、位运算是什么？二、例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。