0x00基础算法 -- 0x01 位运算

资料来源:
算法竞赛进阶指南

活动 - AcWing

1、进制表示

二进制表示:

m位二进制中,通常称最低位为第0位,从右到左以此类推,最高位为第m-1位。

常用十六进制表示的数字:

32位补码int(十进制)int(十六进制)
0000...000000x0
0111...111121474836470x7FFFFFFF
00111111重复四次10611095670x3F3F3F3F
1111...1111-1

0xFFFFFFFF

0x3F3F3F3F的两倍不超过0x7FFFFFFF,即int能表示的最大正整数
初始化一个变量为0x3F3F3F3F,常用memset(a, 0x3F, sizeof(a)),memset是按字节填充,0x7F7F7F7F是memset最大能初始化的数值。当我们需要将一个数组中的数值初始化为正无穷时,常初始化为0x3F3F3F3F。

2、移位运算 

移位运算:


左移:

  • 1 << n = 2^n
  • n << 1 = 2n
     

算术右移:高位以符号位填充,低位越界后舍弃(向下取整还是看向零取整看具体编译器)。
逻辑右移:高位以0填充,低位越界后舍弃。
 

89. a^b - AcWing题库 

思路:

  1. 每个正整数都可以唯一表示为若干指数不重复的2的次幂的和,所以有b = C_{k-1}2^{k-1} + C_{k-2}2^{k-2} +...+ C_{0}2^{0}
  2. 那么有a = a^{C_{k-1}*2^{k-1}} * a^{C_{k-2}*2^{k-2}} *...*a^{C_{0}*2^{0}}
  3. 通过计算可知上试a乘积的数量不多于k = \left \lceil log_{2}(b + 1)) \right \rceil
  4. 由于a^{2^{i}} = (a^{2^{i-1}})^{2},所以a中的每个乘积项我们可以通过迭代获取,通过二进制位上是1或0可以知道该乘积项的C是0还是1
  5. 时间复杂度:取决于k的大小,为O(log_{2}b)
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;int a,b,p;int main()
{cin >> a >> b >> p;int res = 1 % p;while(b){if(b & 1)res = (long long)res * a % p;//a的0~k-1次方依次迭代a = (long long)a * a % p;b >>= 1;}cout << res << endl;return 0;
}

注意:在C++中,数值进行算术运算时,得到是数值类型以参与运算的最高数值类型为准,与保存结果的变量类型无关,即两个32位整数的乘积可能超过int类型的表示范围,但CPU只会用1个32位寄存器保存结果,造成溢出现象,可以通过强转一个变量位64位整数类型long long参与运算,得到正确结果再取模通过隐式类型转换成int类型。

90. 64位整数乘法 - AcWing题库

思路一:

  • 跟上一题一样的方法,先分析正整数的2的次幂的和,再通过迭代的方式获取每一项。
  • b = C_{k-1}2^{k-1} + C_{k-2}2^{k-2} +...+ C_{0}2^{0}
  • a * b = a * C_{k - 1}* 2^{k - 1} + a * C_{k - 2}* 2^{k - 2} + ... + a * C_{0}* 2^{0}
  • 时间复杂度:O(log_{2}b)
#include <iostream>
using namespace std;
typedef long long LL;LL a, b, p;int main()
{cin >> a >> b >> p;LL res = 0;while(b){if(b & 1)res = (res + a) % p;a = a * 2 % p;b >>= 1;}cout << res << endl;return 0;
}

思路二:

  • 利用a * b mod p = a * b - \left \lfloor a * b / p \right \rfloor * p
  • 当a,b < p时,a * b / p下取整以后一定小于p,利用浮点数执行 a * b / p,不关心小数后面的数。
  • \left \lfloor a * b / p \right \rfloor * pa * b可能会很大,超出long long能表示的范围,但二者的差一定在0~p-1之间,我们只需要知道较低位的若干位即可,即使超出范围,舍弃的是高位,不影响低位。
#include <iostream>
using namespace std;
typedef long long LL;LL a, b, p;int main()
{cin >> a >> b >> p;a %= p;b %= p;LL c = (long double)a *b / p;LL res = (a * b) - c * p;if(res < 0)res += p;else if(res >= p)res -= p;cout << res << endl;return 0;
}

3、二进制状态压缩(常用于状态压缩dp)

用一个m位二进制整数来代替一个长度为m的bool数组(优势:节省程序运行的时间和空间)。当m不大时,可以直接用一个整数类型进行存储;当m较大时,可以使用若干个整数类型,或者使用C++STL中的bitset实现。

取整数n在二进制表示下的第k位(n >> k) & 1
取整数n在二进制表示下的第0~k-1位(后k位)n & ((1 << k) - 1)
把整数n在二进制表示下的第k位取反n ^ (1 << k)
对整数n在二进制表示下的第k位赋值1n | (1 << k)
对整数n在二进制表示下的第k位赋值0n & (~(1 << k))

91. 最短Hamilton路径 - AcWing题库 

思路:
暴力枚举:O(n * n!)-- 会TLE

状态压缩dp:用二进制状态压缩优化,达到O(n^{2} * 2^{n})

  • 状态表示:f[ i ][ j ]表示 i 这压缩状态下,且目前处在 j 位置时的最短路径
  • 状态属性:min
  • 状态转移:f[ i ][ j ] = min(f[ i ][ j ], f[ i ^ (1 << j) ][ k ] + weight[ k ][ j ])
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 25;
const int M = 1 << 20;
int weight[N][N];
int f[M][N];//f[i][j]表示在i状态下,且目前处于j位置时的最短路径,1表示已经经过,0表示没有经过
int 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));//因为是从0出发的,所以初始化起始位置--经过第一个点且目前处于第一个点f[1][0] = 0;//状态转移方程:f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + weight[k][j])//起始状态f[1][0],目标状态f[(i << n) - 1][n - 1]for (int i = 1; i < 1 << n; i++) //小状态推向大状态for (int j = 0; j < n; j++)if (i >> j & 1) //i状态下j位置应该是已经经过了for (int k = 0; k < n; k++)if ((i ^ (1 << j)) >> k & 1) //j未被经过的状态k应该已经经过了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;
}

4、成对变换

对于非负整数n:

  • 当n为偶数时,n ^ 1 等于 n + 1
  • 当n为奇数时,n ^ 1 等于 n - 1

通过上述结论可得,”0和1“,”2和3“,”4和5“...关于 ^1 运算构成成对变换

作用:常用于图论邻接表中边集的存储,在具有无向边(双向边)的图中把对正反方向的边分别存储在邻接表数组的第n和第n + 1的位置(n为偶数),就可以通过 ^1 运算获取与当前边(x,y)反向的边(y,x)的存储位置。

5、lowbit运算

公式:

lowbit(n) = n & (~n + 1) = n & (-n)

作用:

1、lowbit(n)返回非负整数n二进制表示下"最低位的1及其后边所有的0"

2、可以得出非负整数在二进制表示下所以是1的位,花费时间与1的个数有关:

  • 朴素做法:每次通过lowbit(n)得到的数进行以2为底的log运算得到的值k就表示第k位就是1,例如:lowbit( 6 ) = lowbit( 110 ) = 10,k = log_{2}(10)_{b} = log_{2}2 = 1,得到第1位是1,以此类推,直到全部求出
  • Hash优化做法:由于C++的math库中log函数是以e为底的运算,并且复杂度常数较大,所以需要预处理一个数组,通过Hash的方法代替log运算。
    当n较小时,可以直接建立一个数组H,令H[2^{k}] = k
    const int MAX_N = 1 << 20;
    int H[MAX_N + 1];
    for(int i = 0; i <= 20; i++)H[1 << i] = i; //预处理
    while(cin >> n) //对多次询问进行求解
    {while(n > 0){cout << H[n & -n] << ' ';n -= n & (-n);}cout << endl;
    }

    效率更高的方法:建立一个长度为37的数组H,令H[2 ^ k mod 37]  = k(数学小寄敲:对于任意的k属于[ 0,35 ],2^k mod 37互不相等,且恰好取遍整数 1 ~ 36
     

    int H[37];
    for(int i = 0; i < 36; i++)H[(1ll << i) % 37] = i;
    while(cin >> n)
    {while(n > 0){cout << H[(n & -n) % 37] << ' ';n -= n & -n;}cout << endl;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/10245.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

算法求解(C#)-- 寻找包含目标字符串的最短子串算法

1. 引言 在字符串处理中&#xff0c;我们经常需要从一个较长的字符串中找到包含特定目标字符串的最短子串。这个问题在文本搜索、基因序列分析等领域有着广泛的应用。本文将介绍一种高效的算法来解决这个问题。 2. 问题描述 给定一个源字符串 source 和一个目标字符串 targe…

Linux之Chronyd 时间服务器配置(Chronod Time Server Configuration in Linux)

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 本人主要分享计算机核心技…

【Ant Design Pro】如何实现组件的状态保存umi-plugin-keep-alive插件的使用

都知道vuejs里面帮我们实现了一个内置的keep-alive组件&#xff0c;给我们缓存一些组件的状态带来了很大的便利。但是在react中没有自带的实现&#xff0c;可以借助社区的插件umi-plugin-keep-alive来实现这个功能。 实现效果对比 未使用插件&#xff0c;可以看到我们在页面跳…

【数据结构】二叉排序树和平衡二叉树

目录 1. 二叉搜索树&#xff08;BST&#xff09; 1.1 二叉搜索树的定义及特点 1.1.1 定义 1.1.2 特点 1.2 二叉排序树的构造&#xff08;创建&#xff09; 1.2.1 基本思想 1.2.2 算法 1.3 二叉排序树的删除 2. 平衡二叉树&#xff08;AVL&#xff09; 2.1 为什么要用…

C++四种类型转换

C语言提供了四种类型转换 const_cast: 可以去除掉常量属性的类型转换 //const_cast const int a 10; double* p1 (double*)&a;//类型和原来的类型可以不一致&#xff0c;但是不安全 int* p2 const_cast<int*>(&a);//类型和原本的类型必须匹配 //<>中必…

【SPIE出版,往届稳定EI检索】2024智能视觉与数据建模国际学术会议(ICIVD 2024,12月13-15日)

2024智能视觉与数据建模国际学术会议 2024 International Conference on Intelligent Vision and Data modeling (ICIVD 2024) 重要信息 会议官网&#xff1a;www.iccaid.net 2024 International Conference on Intelligent Vision and Data modeling (ICIVD 2024)www.iccaid…

大模型的思维链提示

文章目录 思维链提示的基本形式思维链提示的优化策略关于思维链的进一步讨论思维链提示是一种高级提示策略,旨在增强大语言模型在各类复杂推理任务上的表现。常见的推理任务包括算术推理、常识推理以及符号推理等多种任务。与上下文学习方法仅使用⟨输入,输出⟩二元组来构造提…

JavaScript day01 笔记

一、引入方式 JavaScript 程序不能独立运行&#xff0c;它需要被嵌入 HTML 中&#xff0c;然后浏览器才能执行 JavaScript 代码。通过 script 标签将 JavaScript 代码引入到 HTML 中 1️⃣内部 通过 script 标签包裹 JavaScript 代码&#xff08;一般就写在</script>的…

vue,uniapp,微信小程序解决字符串中出现数字则修改数字样式,以及获取字符串中的数字

简单记录一下&#xff0c;最近遇到的一个新需求&#xff1a;后端返回的是非富文本&#xff0c;只是一串字符串&#xff0c;其中包含了文字和数字&#xff0c;前端需要将出现数字的地方将其加粗或者修改颜色等需求 设计思路&#xff1a;&#xff08;简单做个记录方便以后理解&a…

数据分析:16s差异分析DESeq2 | Corncob | MaAsLin2 | ALDEx2

禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍DESeq2原理计算步骤结果Corncob原理计算步骤结果MaAsLin2原理计算步骤结果ALDEx2原理计算步骤结果加载R包数据链接数据预处理微生物数据样本信息提取物种名称过滤零值保留结果读取…

【CSS】标准怪异盒模型

概念 CSS 盒模型本质上是一个盒子&#xff0c;盒子包裹着HTML 元素&#xff0c;盒子由四个属性组成&#xff0c;从内到外分别是&#xff1a;content 内容、padding 内填充、border 边框、外边距 margin 盒模型的分类 W3C 盒子模型(标准盒模型) IE 盒子模型(怪异盒模型) 两种…

C++builder中的人工智能(18):神经网络中的SoftMax函数

在这篇文章中&#xff0c;我们将探讨SoftMax函数在神经网络中的作用&#xff0c;如何在人工神经网络&#xff08;ANN&#xff09;中使用SoftMax函数&#xff0c;以及在AI技术中SoftMax的应用场景。让我们来详细解释这些概念。 SoftMax函数是什么&#xff1f; SoftMax函数是逻辑…

机器学习(七)——集成学习(个体与集成、Boosting、Bagging、随机森林RF、结合策略、多样性增强、多样性度量、Python源码)

目录 关于1 个体与集成2 Boosting3 Bagging与随机森林4 结合策略5 多样性X 案例代码X.1 分类任务-Adaboost-SVMX.1.1 源码X.1.2 数据集&#xff08;鸢尾花数据集&#xff09;X.1.3 模型效果 X.2 分类任务-随机森林RFX.2.1 源码X.2.2 数据集&#xff08;鸢尾花数据集&#xff09…

Matlab轻松烟雾检测

小编经验分享&#xff1a;如何使用Matlab进行烟雾检测 烟雾检测是一项重要的安全技术&#xff0c;它可以帮助我们及时发现火灾风险并采取相应的措施。在这篇文章中&#xff0c;小编将和大家分享如何使用Matlab进行烟雾检测的经验。希望这些经验对大家在实际应用中能够有所帮助…

c语言其实很简单----【数组】

TOC 1.输入10个学生成绩&#xff0c;计算及格人数&#xff0c;平均成绩&#xff0c;总成绩。 #include<stdio.h> int main(){float score[10];int i ,cut;float avar0.0,sum0.0;for(i0;i<10;i)scanf("%f",&score[i]);//输入10个学生的成绩cut0;for(i0…

在 .NET 6.0 中创建用于 CRUD 操作的 Web API

快速概述&#xff1a; 在动态的技术世界中&#xff0c;创建强大的 Web API 已成为开发人员不可或缺的关键技能。这些 API 是促进不同应用程序之间顺畅通信的重要链接&#xff0c;可实现无缝数据检索和操作。本文的重点是在 .NET 6 中为 CRUD 操作创建 Web API。 为了实现这一点…

lua 编译网路核心

下载 Severity Code Description Project File Line Suppression State Details Error LNK1104 cannot open file lua53.lib mime D:\MyWork\lua\luasocket-master\luasocket-master\LINK 1 2> Creating library Release\soc…

SystemC学习(4)— 在VCS中运行SystemC

SystemC学习&#xff08;4&#xff09;— 在VCS中运行SystemC 一、前言 参考&#xff1a;VCS编译verilog&SystemC 二、仅包含SystemC的仿真 源文件使用上一篇&#xff1a;SystemC学习&#xff08;3&#xff09;— APB_SRAM的建模与测试 编写makefile如下所示&#xff…

Qt第三课 ----------布局

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…

MySQL本地安装及密码重置常见错误处理

文章目录 一、MySQL下载二、配置环境变量三、MySQL初始化1.初始化MySQL数据库2.安装MySQL服务3.启动MySQL服务 四、密码重置 一、MySQL下载 官网地址&#xff1a;https://dev.mysql.com/downloads/mysql/5.5.html#downloads 下载完成后&#xff0c;直接解压缩到D盘 二、配置…