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

本文共 4222 字,大约阅读时间需要 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

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.11.158.89]2022年05月23日 19时43分44秒