算法竞赛-基础算法-位运算

ops/2025/3/18 16:37:38/

目录

1.快速幂

2.快速乘

3.lowbit(n)

4.其他

5.相关题目

6.小结


引言:位运算的主要特点之一是在二进制表示下不进位,一下为一些基础的位运算操作:

异或
and,&or,|not,~xor

1.快速幂

快速幂的计算原理就是基于位运算,把阶乘的数当作二进制一个个拆分掉

//快速幂
long long quick_pow(long long a, long long n, long long p)//相当于计算(a ^ b) mod p
{long long res = 1;while (n){if (n & 1) res = (res * a) % p;n /= 2;a = (a * a) % p;}return res % p;
}

每次n都会向左移位,如果这位是1的话就将这个数乘到res中,再让基数进行平方,每次运算后要进行取模,这样就是一个很完整的快速幂

2.快速乘

如果遇上a*b%p,其1\leq a,b\leq10^{18},这时候就要用到快速乘了,如果直接进行运算的话会导致超过long long最大的限制

//快速乘,64位
long long mul(long long a, long long n, long long p)//相当于计算(a * n) mod p
{long long res = 0;while (n){if (n & 1) res = (res + a) % p;n /= 2;a = (a * 2) % p;}return res;
}

这个代码的写法同上,都是利用的位运算来进行乘法

3.lowbit(n)

位运算还有一个最重要的就是lowbit(n),lowbit(n)定义为n在二进制表示下"最低位的1以及后边所有的0。

#define lowbit(x) x&-x

因为lowbit(n)=n&(~n+1)=n&(-n),所以就可以利用以上定义

lowbit(n)运算配合hash可以找到整数二进制表示下所有是1的位。

//任意k属于[0,35],2的k次方mod37互不相等,且恰好取遍整数1-36
int H[37];
int n;
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;
}

这个效率十分高效,几乎相当于o(1)。

lowbit(n)运算也是树状数组中一个基本运算,这个之后再讲、

4.其他

位运算还有一些相关的库函数,不过并非C语言标准,最好不要随便使用

int __builtin_ctz(unsigned int x);
int __builtin_ctzll(unsigned long long x);
//返回x的二进制表示下最低位的1后边有多少0int __builtin_popcount(unsigned int x);
int __builtin_popcountll(unsigned long long x);
//返回x的二进制表示下有多少位为1

5.相关题目

快速幂的模板题

P1226 【模板】快速幂 - 洛谷

快速乘的模板题

P10446 64位整数乘法 - 洛谷

还有一道位运算相关的题目

P2114 [NOI2014] 起床困难综合症 - 洛谷

这个题目就单独考虑每一位,这样时间复杂度就是O(30*n),以下是代码和解释

#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
string b[N];
int n, m;
int calc(int bit, int now)//计算所有运算后对这意味的影响
{for (int i = 1; i <= n; i++){int x = a[i] >> bit & 1;if (b[i] == "AND") now &= x;else if (b[i] == "OR") now |= x;else now ^= x;}return now;
}
int main()
{cin >> n >> m;int sum = 0, ans = 0;for (int i = 1; i <= n; i++)cin >> b[i] >> a[i];for (int bit = 30; bit >= 0; bit--){int res0 = calc(bit, 0);int res1 = calc(bit, 1);if (sum + (1 << bit) < m && res0 < res1)//如果超过m并且取1比取0有用sum += 1 << bit, ans += res1 << bit;else ans += res0 << bit;}cout << ans << endl;
}

6.小结

这就是这一节的全部内容了,期待下一节


http://www.ppmy.cn/ops/166815.html

相关文章

C# Type类中Name、FullName、Namespace、AssemblyQualifiedName的区别

总目录 前言 在C#中&#xff0c;Type 类提供了多种属性来获取类型的相关信息。以下是 Name、FullName、Namespace 和 AssemblyQualifiedName 这几个属性的区别和具体用途。 一、获取各名称属性示例 namespace ReflectionDemo {public class User { }internal class Program{s…

使用yolov8+flask实现精美登录界面+图片视频摄像头检测系统

这个是使用flask实现好看登录界面和友好的检测界面实现yolov8推理和展示&#xff0c;代码仅仅有2个html文件和一个python文件&#xff0c;真正做到了用最简洁的代码实现复杂功能。 测试通过环境&#xff1a; windows x64 anaconda3python3.8 ultralytics8.3.81 flask1.1.2…

《大语言模型》学习笔记(三)

GPT系列模型的技术演变 2022 年11月底&#xff0c;OpenAI推出了基于大语言模型的在线对话应用—ChatGPT。由于具备出色的人机对话能力和任务解决能力&#xff0c;ChatGPT一经发布就引发了全社会对于大语言模型的广泛关注&#xff0c;众多的大语言模型应运而生&#xff0c;并且…

优化Go错误码管理:构建清晰、优雅的HTTP和gRPC错误码规范

在系统开发过程中&#xff0c;如何优雅地管理错误信息一直是个棘手问题。传统的错误处理方式往往存在不统一、难以维护等缺点。而 errcode 模块通过对错误码进行规范化管理&#xff0c;为系统级和业务级错误提供了统一的编码标准。本文将带您深入了解 errcode 的设计原理、错误…

uni-app+SpringBoot: 前端传参,后端如何接收参数

做项目中的一些小经验&#xff0c;方便后续 &#xff08;1&#xff09;前端代码中&#xff0c;请求的 URL 是通过查询参数&#xff08;?id${articleId}&#xff09;传递的 后端接口&#xff1a; GetMapping("/knowledgeDetail") public Result getKnowledgeByid(R…

深度解读 | AI驱动下的新型金融对冲策略:稀疏奖励强化学习的应用

“HEDGING WITH SPARSE REWARD REINFORCEMENT LEARNING” 论文地址&#xff1a;https://arxiv.org/pdf/2503.04218 摘要 尽管衍生品作为金融工具在风险管理和提升市场效率方面扮演着关键角色&#xff0c;但传统的对冲模型在处理复杂多变的市场环境时往往显得力不从心。为了应对…

Couchbase Analytics 的结构

Couchbase Analytics 的结构 Couchbase Analytics 服务专为大规模、并发、复杂的分析查询而设计&#xff0c;同时不会影响事务性工作负载的性能。下面将详细介绍其结构和架构&#xff0c;以帮助您深入理解 Couchbase Analytics 的运作方式。 1. Couchbase 集群架构 Couchbase…

uniapp笔记-底部和首部标签页菜单生成

逻辑 这些都是需要配置pages.json文件。 其中底部需要手动配置tarBar&#xff0c;如&#xff1a; "tabBar": {"list":[{"pagePath": "pages/index/index","text": "首页"},{"pagePath": "pages/…