0X01 ——位运算

大家好，欢迎来到IT知识分享网。

一：

“与”运算 ： &；

“或”运算 ： |；

“非”运算 ： ~；

“异或”运算：^;

二：补码

（1）32位无符号整数：unsigned int ; 0 ~ ;

（2）32位有符号整数：int; – ~ ；在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

比如，十进制中的数 +3 ，计算机字长为8位，转换成二进制就是00000011。如果是 -3 ，就是 。

具体请见：

0X01 ——位运算

三：移位运算；

（1）左移：

把左移运算符(<<)左边的运算数的各二进制位全部左移若干位，移动的位数由左移运算符右边的数指定，高位舍掉，低位补0。

（2）右移：

把右移运算符(>>)左边的运算数的各二进制位全部右移若干位，移动的位数由右移运算符右边的数指定;

对于有符号数，在右移时，符号位将随同移动：

当有符号数为正数时，最高位补0

当有符号数为负数时，最高位也就是符号位为1，最高位补0或者补1，取决于编译系统。（很多系统规定为补1）。

通俗理解：

• 左移将原数乘以2
• 右移将原数除以2

举例：

a. 原数： 100
整型是4字节32位，将100以整型的二进制表示
二进制： 00000000 00000000 00000000 0

b. 原数： 75
二进制： 00000000 00000000 00000000 0

觉得理解了，可以尝试一下下面这道题；

求 a 的 b 次方对 p 取模的值。

输入格式 

三个整数 a,b,p ,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

输入样例：

3 2 7 

输出样例：

2

解题思路：

（1）b可用二进制表示为：

所以：

 （2）

b & 1运算可以取出b在二进制表示下的最低位，而b >> 1运算可以舍去最低位。

AC代码：

​ #include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { long long a, b, p; cin >> a >> b >> p; long long ans = 1 % p; for(; b ; b >>= 1) { if(b & 1) ans = ans * a % p; a = a * a % p; } cout << ans << endl; return 0; } ​

还可以尝试一下acwing 90.

四：二进制状态压缩

具体可以参考acwing 91.

给定一张 n 个点的带权无向图，点从0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n。

接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

输入样例：

5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0 

输出样例：

18

AC代码：

#include <bits/stdc++.h> using namespace std; const int N = 20; int n; int a[N][N]; int f[1 << N][N]; int main() { cin >> n; for(int i = 0; i < n; i ++ ) { for(int j = 0; j < n; j ++ ) { cin >> a[i][j]; } } memset(f, 0x3f, sizeof f); f[1][0] = 0; //终点是j 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 ++ )/*上一种情况，又因为 j 只能恰好经过一次，所以一定是刚刚经过的，所以在上一时刻“被经过点的状态”对应的二进制的第 j 为应该赋值为 0 ，即 i ^ (1 << j)*/ { if((i ^ 1 << j) >> k & 1) { f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + a[k][j]); } } } } } cout << f[(1 << n) - 1][n - 1]; return 0; } 

五：成对变换

对于非负整数 n : 

当 n 为偶数时，n ^ 1 等于 n + 1;

当 n 为奇数时，n ^ 1 等于 n  – 1;

因此，“0 与1” “2 与3” “4与5” 。。。关于 ^ 1 运算构成“成对变换”。

六：lowbit运算

可以理解为：返回 x 的最后一位1；

应用：统计一下 x 里面 1 的个数

lowbit(n) =  n & (~ n + 1) = n & ( – n)。

#include <bits/stdc++.h> using namespace std; int lowbit(int x) { return x & (-x); } int main() { int x; cin >> x; int res = 0; while(x) { res ++; x -= lowbit(x); } cout << res << endl; return 0; }