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.rhkb.cn/news/467903.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

H5移动端预览PDF方法

新建页面 新建一个页面以便去预览对应的pdf 新建完后在 pages.json 文件内去新增对应路由 页面内容 <template><view class"page"><view class"pdf"><view id"demo"></view></view><view class"b…

嵌入式开发之线程

进程 vs 线程 进程在切换时系统开销大很多操作系统引入了轻量级进程LWP同一进程中的线程共享相同地址空间Linux不区分进程、线程(都会创建:task_strcut)线程特点: 通常线程指的是共享相同的地址空间的多个任务,使用多线程的好处 大大提高了任务切换的效率避免了额外的TLB…

【SQL实验】更新操作

完整代码在文章末尾【代码是自己的解答&#xff0c;并非标准答案&#xff0c;也有可能写错&#xff0c;文中可能会有不准确或待完善之处&#xff0c;恳请各位读者不吝批评指正&#xff0c;共同促进学习交流】 将素材“图书管理”文件下载到本地&#xff0c;并将其还原到SQL SER…

Hadoop(HDFS)

Hadoop是一个开源的分布式系统架构&#xff0c;旨在解决海量数据的存储和计算问题&#xff0c;Hadoop的核心组件包括Hadoop分布式文件系统&#xff08;HDFS&#xff09;、MapReduce编程模型和YARN资源管理器,最近需求需要用到HDFS和YARN。 文章目录 HDFS优缺点HDFS的读写原理 常…

Spire.PDF for .NET【页面设置】演示:获取 PDF 文件中的页数

计算 PDF 文件中的页数对于各种目的都至关重要&#xff0c;例如确定文档长度、组织内容和评估打印要求。除了使用 PDF 查看器了解页数信息外&#xff0c;您还可以通过编程自动执行该任务。在本文中&#xff0c;您将学习如何使用C#通过Spire.PDF for .NET获取 PDF 文件中的页数。…

stm32不小心把SWD和JTAG都给关了,程序下载不进去,怎么办?

因为想用STM32F103的PA15引脚&#xff0c;调试程序的时候不小心把SWD和JTAD接口都给关了&#xff0c;先看下罪魁祸首 GPIO_PinRemapConfig(GPIO_Remap_SWJ_JTAGDisable,ENABLE);//关掉JTAG&#xff0c;不关SWGPIO_PinRemapConfig(GPIO_Remap_SWJ_Disable, ENABLE);//关掉SW&am…

vue3使用element-plus,树组件el-tree增加引导线

vue3使用element-plus&#xff0c;树组件el-tree增加引导线 vue3项目element-plus&#xff0c;树组件el-tree增加引导线 element-plus组件库的el-tree样式 因为element的样式不满足当前的的需求&#xff0c;UI图&#xff0c;所以对el-tree进行增加了引导线 修改样式如下&am…

pytest简单使用

一&#xff1a;Mark 1.注册标记 在项目根目录下创建固定名为 pytest.ini 的配置文件&#xff0c;文件格式需要加上 [pytest] &#xff0c;然后通过 markers 注册自定义标记 2.贴上标记 通过pytest加上装饰器&#xff0c;然后pytest.mark.XX配置自定义的标记&#xff0c;一个…

【C++】——多态

一.多态的概念 1.多态 多态(polymorphism)的概念&#xff1a;通俗的来说&#xff0c;就是多种形态。多态分为静态多态(编译时多态)和动态多态(运行时多态)&#xff0c;而我们讲的多态大部分都是动态多态。 静态多态主要就是我们前面了解过的函数模板和函数重载&#xff0c;它…

Linux基础4-进程4(环境变量,命令行参数详解)

上篇文章:Linux基础4-进程3(进程优先级&#xff0c;竞争&#xff0c;独立&#xff0c;并行&#xff0c;并发&#xff0c;进程切换)-CSDN博客 本章重点: Linux中环境变量的理解和使用 目录 一. 环境变量概念和查看环境变量 1.1 环境变量概念 1.2 查看环境变量 二. 获取环境变…

【复平面】-复数相乘的几何性质

文章目录 从数学上证明1. 计算乘积 z 1 ⋅ z 2 z_1 \cdot z_2 z1​⋅z2​2. 应用三角恒等式3. 得出结果 从几何角度证明1.给出待乘的复数 u i u_i ui​2.给出任意复数 l l l3.复数 l l l 在不同坐标轴下的表示图 首先说结论&#xff1a; 在复平面中&#xff0c;两个复数&a…

如何将现有VUE项目所有包更新到最新稳定版

更新有风险,Enter要谨慎!!! 要将项目中的所有 npm 包更新到最新稳定版&#xff0c;可以使用 npm-check-updates 工具。以下是具体步骤&#xff1a; 步骤一&#xff1a;安装 npm-check-updates 首先&#xff0c;全局安装 npm-check-updates 工具&#xff1a; npm install -g…

excel常用技能

1.基础技能 1.1 下拉框设置 a. 选中需要设置的列或单元格&#xff0c;数据 ---》 数据验证 b.验证条件 ---> 序列&#xff08;多个值逗号隔开&#xff09; 2.函数 2.1 统计函数-count a.count(区域&#xff0c;区域&#xff0c;......) 统计数量&#xff0c;只针…

(linux驱动学习 - 12). IIC 驱动实验

目录 一.IIC 总线驱动相关结构体与函数 1.i2c_adapter 结构体 2.i2c_algorithm 结构体 3.向系统注册设置好的 i2c_adapter 结构体 - i2c_add_adapter 4.向系统注册设置好的 i2c_adapter 结构体 - i2c_add_numbered_adapter 5.删除 I2C 适配器 - i2c_del_adapter 二.IIC 设…

华为ensp防火墙配置(纯享版)

文章目录 前言一、拓扑结构二、配置步骤1.路由器配置&#xff08;路由器代替互联网&#xff09;2.server和pc配置3.防护墙配置4.测试 总结 前言 防火墙是生活和项目中不可或缺的一部分&#xff0c;本篇文章对华为的ensp防火墙配置做一个总结。在之前的dhcp配置中有软件的下载地…

996引擎 - 活捉NPC

996引擎 - 活捉NPC 引擎触发 - 引擎事件(QF)事件处理模块 GameEvent测试文件参考资料 引擎触发 - 引擎事件(QF) cfg_game_data 配置 ShareNpc1 可以将QM和机器人的触发事件全部转到 QF 引擎触发是通用的,TXT的所有触发转换成小写后在LUA中就可使用,如说明书中缺省可反馈至对接群…

如何借助AI 来提高开发效率

前言 随着人工智能&#xff08;AI&#xff09;技术的快速发展&#xff0c;特别是大规模语言模型&#xff08;如 GPT 系列&#xff09;的崛起&#xff0c;软件开发领域正在经历一场革命。AI 大模型不仅在代码生成方面展现出强大的能力&#xff0c;还在测试、维护和创新等多个环…

QML项目实战:自定义Button

目录 一.添加模块 ​1.QtQuick.Controls 2.1 2.QtGraphicalEffects 1.12 二.自定义Button 1.颜色背景设置 2.设置渐变色背景 3.文本设置 4.点击设置 5.阴影设置 三.效果 1.当enabled为true 2.按钮被点击时 3.当enabled为false 四.代码 一.添加模块 1.QtQuick.Con…

HarmonyOS NEXT应用元服务开发Intents Kit(意图框架服务)本地搜索接入方案

一、方案概述 当用户使用应用/元服务时&#xff0c;开发者可以按照标准意图Schema向系统共享数据&#xff0c;并支持意图调用&#xff08;空调用与传参调用&#xff09;&#xff0c;以实现用户点击卡片后&#xff0c;可后台执行功能&#xff08;例如播放指定歌曲&#xff09;或…

CyclicBarrier使用详解及遇到的坑

上一篇文章讲的是关于是使用CountDownLatch实现生成年底报告遇到的问题&#xff0c;这个计数器和CyclicBarrier也有类似功能&#xff0c;但是应用场景不同。 一、应用场景 CountDownLatch&#xff1a; 有ABCD四个任务&#xff0c;ABC是并行执行,等ABC三个任务都执行完…