再谈位运算
发布日期:2022-02-24 01:06:49 浏览次数:23 分类:技术文章

本文共 4283 字,大约阅读时间需要 14 分钟。

再谈位运算


位运算基础:

基本运算:

与 : x & y 只要有一个为 0 即为 0, 都为 1 为 1
或: x | y 只要有一个为 1 即为 1, 都为 0 为 0
非 : ! x 取反
异或 : x ^ y 加法不进位, 相同为0, 不同为1

int 32位 :

1: 0000000000…1

2: 0000000000…10

3: 0000000000…11

补码: 一个数与 x 相加 为 0, 则这个数即为 x 的补码, 等于 x 取反 + 1, 也可以用 0 减去 x 得到

1 + x = 0000000000000000

1 + 1111111111111111111 = 0000000000…00

2 + 1111111111111111110 = 0000000000…00

x + ? = 000000000000…00

? 即为 x 的补码 :

求? : ? = ~x + 1

由此可得: -n = ~n + 1

优点 : 根据此原理在计算机中可以通过加法来实现减法

例子:

初始化数组为正无穷 : memset(f, 0x3f, sizeof (f) );

memset是按字节进行复制, int数组每个元素为 4 个字节, 故复制后每个元素为 0x3f3f3f3f

当数组中两个元素相加的时候, 0x3f3f3f3f * 2 < 0xffffffff

此时不会发生溢出错误

重要运算: 位运算

左移: 1 << n = 2 n 2^n 2n

右移: n >> x = n ÷ 2 x n \div {2^x} n÷2x 当右移的时候, 最左边的数被移除, 最高位补齐, 算术右移为补上它的符号位, 负数补1, 正数补0


例题解析:

1. a ^ b

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

输入格式

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

输出格式

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

数据范围

0 ≤ a , b ≤ 1 0 9 0 \le a,b \le {10^9} 0a,b109

1 ≤ p ≤ 1 0 9 1 \le p \le {10^9} 1p109

输入样例:

3 2 7

输出样例:

2

思路 : 快速幂, 将 b 拆分成二进制, 通过右移操作查看 b 的每一位, 同时 a 左移, 如果此位为 1 就乘上 a

**代码如下 : **

#include 
using namespace std ; int main() {
int a, b, p ; cin >> a >> b >> p ; int res = 1 % p ; // 这里 mod p 是为了防止 b 为 0, p 为 1 这组数据 while (b) {
if (b & 1) res = res * 1ll * a % p ; // 这里乘 1ll 的目的是将res转换为长整型, 防止溢出 a = a * 1ll * a % p ; b >>= 1 ; } cout << res << endl ; return 0 ; }
2. 64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式

第一行输入整数a,第二行输入整数b,第三行输入整数p。

输出格式

输出一个整数,表示a*b mod p的值。

数据范围

1≤a,b,p≤ 1 0 18 {10^{18}} 1018

输入样例:

3
4
5
输出样例:
2

思路: 快速幂思想, 两个64位的数相乘为128位, 必然溢出, 相加不溢出 --> 把乘法变成加法

a * b

a + a + a + … + a

a * 1 = a

a * 2 = 2a = a + a

a * 4= 4a = 2a + 2a

a * 8 = 8a = 4a + 4a

a * (2 ^ k) = 2^k * a

代码如下:

#include 
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 + a) % p ; // a * 2 % p 也可 } cout << res << endl ; return 0 ;}
3.最短Hamilton路径 (NP完全问题)

旅行商问题

NP完全问题: NP完全问题(NP-C问题),是之一。 NP的英文全称是Non-deterministic Polynomial的问题,即复杂程度的问题。简单的写法是 NP=P?,问题就在这个上,到底是NPP,还是NP不等于P。

因此只能通过暴力 (直接暴力会TLE) 优化的方法求解

给定一张 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 路径的长度。

数据范围

1≤n≤20
0≤a[i,j]≤ 1 0 7 10^7 107

输入样例:

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

思路:

假设遍历 0, 1, 2, 3这四个点

0 -> 1-> 2 -> 3 18

0 -> 1-> 2 -> 3 20

根据以上两种遍历方式可知, 当到第三个点的时候, 此时第一种方式的路径长度比第二种方式的少2

又因为从 3 号点遍历其他剩余的点的可能方式是相同的, 所以接下来第二种方式的每一种遍历方式都会比

第一种方式的遍历方式多 2, 因此 此时我们不需要再遍历第二种方式

两个关键点:

  1. 哪些点被用过;
  2. 目前停止哪个点上

第一维状态 : 2^20

第二维状态 : 20

数量 (时间复杂度) --> 2 ^ 20 * 20 = 2 * 10 ^ 7

考虑每个状态怎么被计算:

state表示哪些点被用过, j表示当前停在哪个点上

假设从 k 转移过来:

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

集合表示当前状态已经遍历过的点

state_k 里面需要包含 k

状态压缩

用一个二进制的整数来表示我们的 state

是一个20位的整数 00…0

某一位为 1 表示这个点存在, 为 0 表示这个点不存在

假设现在 包含了 0, 1, 4 这三个点

state = 10011

整个程序复杂度 = 状态数量 * 状态转移复杂度

2 * 10 ^ 7 * 20

题目的 时/空限制:5s / 256MB 5s == 5亿次

我们这里程序的复杂度约为 4亿次 能够通过

代码如下:

#include 
#include
#include
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) // 判断当前状态是否合法, 判断 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 ; }

异或 ^

  1. 实现 成对的 思想

0, 1

2, 3

4, 5

6, 7

0 ^ 1 = 1, 1 ^ 1 = 0

4 ^ 1 = 5, 5 ^ 1 = 4

也就是说将 每一个整数异或 1 即可得到它的配偶

作用: 图论中的最小费用流, 在用数组模拟邻接表存边的时候, 需要存一条边以及其反向边, 此时需要快速求出某一条边的反向边, 一般会将一条边的正向边与反向边放在一起

  1. lowbit运算

树状数组基础

快速求出一个整数 n 在二进制中最低的一位 1 是哪个

lowbit(11001000) = 1000

​ 00111000

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

转载地址:https://blog.csdn.net/weixin_45877540/article/details/116210941 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:java简单实用的阿里云短信验证码后端API案例
下一篇:java后端-携带String参数请求URL

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月18日 21时33分29秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql 行转列 显示_mysql 行转列 (结果集以坐标显示) 2019-04-21
由于连接方在一段时间后没有正确答复或连接的主机_新风换气机使用效果不佳,为何?掌握正确使用方法就好了... 2019-04-21
mysql 查询姓王_MySQL查询语句练习题,测试足够用了 2019-04-21
mysql多实例脚本_mysql多实例脚本 2019-04-21
python如何生成excel文件夹_用python脚本通过excel生成文件夹树结构 2019-04-21
python获取post请求中的所有参数_Django从POST reques获取请求参数 2019-04-21
mysql加密复制_MySQL主从复制使用SSL加密 2019-04-21
python启动远端 exe_python打包exe开机自动启动的实例(windows) 2019-04-21
java当前路径_java获取当前路径的几种方法 2019-04-21
java web传递参数_Javaweb的八种传值方式 2019-04-21
java gui支持的包有哪两个_Java GUI 2019-04-21
java list详解_java集合List解析 2019-04-21
java坐标代码_java实现计算地理坐标之间的距离 2019-04-21
kettle调用java程序_Kettle ETL调用 java代码来进行数据库的增删改查 2019-04-21
mysql 取两个时间差 php_在php和MySql中计算时间差的方法详解 2019-04-21
mysql 重启数据库实例_mysql 单机多实例重启数据库服务 2019-04-21
collator java_Java Collator getInstance(Locale)用法及代码示例 2019-04-21
dtc mysql_DTCC归来-高可用可扩展数据库架构探讨 2019-04-21
java怎样将日期本土化_Java中的日期操作 2019-04-21
java生产者消费者模型到精通_java生产者消费者模型 2019-04-21