当前位置：首页 > news >正文

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

news 来源：原创 2025/8/12 10:58:13

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.小结

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

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

目录 1.快速幂 2.快速乘 3.lowbit(n) 4.其他 5.相关题目 6.小结引言：位运算的主要特点之一是在二进制表示下不进位，一下为一些基础的位运算操作： 与或非异或and,&or,|not,~xor 1.快速幂快速幂的计算原理就是基于位运算&#x…...

编程日记 2025/8/12 10:58:13

DeepSeek 助力 Vue3 开发：打造丝滑的表格（Table）之添加导出数据功能

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏+关注哦 💕 目录 DeepSeek 助力 Vue3 开发：打造丝滑的表格（Table）之添加导出数据功能📚页面效果📚指令输入�…...

编程日记 2025/8/11 23:33:24

深入解析音频编解码器（Audio CODEC）：硬件、接口与驱动开发

音频编解码器（Audio CODEC）是音频处理系统中的核心组件，负责模拟信号与数字信号的相互转换，广泛应用于智能音箱、嵌入式系统、消费电子产品等设备。本篇文章将从硬件结构、接口解析、驱动开发和软件配置等方面，…...

编程日记 2025/8/9 15:42:20

什么是 Fisher 信息矩阵

什么是 Fisher 信息矩阵 Fisher 信息矩阵是统计学和机器学习中一个重要的概念，它用于衡量样本数据所包含的关于模型参数的信息量。伯努利分布示例问题描述假设我们有一个服从伯努利分布的随机变量 X X X，其概率质量函数为 P ( X ...

编程日记 2025/8/12 10:56:24

【项目合集】智能语音小车-微信小程序控制

功能需求： 车子检测环境温度、湿度，上报 APP、WEB 端显示实时数据可通过 APP 控制小车前进、左转、右转可通过语音控制小车前进后退车上一个 LED 灯，可通过 WEB、小程序控制在 APP、WEB 上均可注册登录硬件清单硬件功能备注 ESP32 …...

编程日记 2025/8/7 20:26:42

Vue3项目中可以尝试封装那些组件

在 Vue 3 项目中，组件的封装可以根据功能、复用性和业务需求进行划分。以下是一些常见的组件类型，适合封装为独立组件： 1. 基础 UI 组件按钮 (Button) 封装不同样式、大小、状态的按钮。支持 disabled、loading 等状态。输入框 (Input) 封…...

编程日记 2025/8/11 21:34:06

Leetcode——151.反转字符串中的单词

题解一思路最开始的想法是把一个字符串分为字符串数组，但是不知道一共有几个单词（当时没想起来split()），所以选择了用ArrayList储存字符串，在输出时没有考虑ArrayList可以存储空字符串，所以最开始的输出…...

编程日记 2025/8/3 12:42:23

Deepseek+QuickAPI：打造 MySQL AI 智能体入门篇（一）

目录一、什么是 MySQL AI 智能体？ 二、准备工作：认识工具 1. Deepseek 的大模型能力 2. QuickAPI 的功能 3. MySQL 数据库三、动手实践：用自然语言打造智能体 1. 创建一个用户表 2. 添加样本数据 3. 执行查询四、效果展示五、…...

编程日记 2025/8/8 7:42:13

Redis系列：深入理解缓存穿透、缓存击穿、缓存雪崩及其解决方案

在使用Redis作为缓存系统时，我们经常会遇到“缓存穿透”、“缓存击穿”和“缓存雪崩”等问题，这些问题一旦出现，会严重影响应用性能甚至造成服务不可用。因此，理解这些问题的产生原因和解决方案非常重要。本文将全面讲解缓存穿透…...

编程日记 2025/8/9 1:35:20

python局部变量和全局变量

文章目录 1.局部变量和全局变量2.局部变量2.1 局部变量的作用2.2 局部变量的生命周期 3. 全局变量3.1 函数不能直接修改全局变量的引用3.2 在函数内部修改全局变量的值3.3 全局变量定义的位置3.4 全局变量命名的建议 1.局部变量和全局变量 （1）局部变量 …...

编程日记 2025/7/30 12:31:18

⭐算法OJ⭐两数之和【哈希表】（C++ 实现）Two Sum

“两数之和”（Two Sum）是一道非常经典的算法题目，几乎是算法入门和面试准备的必做题之一。它的经典性体现在以下几个方面： 1. 算法入门的基础题目这道题目是许多初学者接触哈希表（Hash Table） 或字典&…...

编程日记 2025/8/6 5:11:10

【AVRCP】Notification PDUs 深入解析与应用

目录一、Notification PDUs 概述二、GetPlayStatus：同步查询播放状态 2.1 命令功能与应用场景 2.2 请求格式（CT → TG） 2.3 响应格式（TG → CT） 2.4 注意事项 2.5 协议实现示例（伪代码）三、RegisterNotification：异步事件订阅 3.1 命令概述 3.2 命令格式 …...

编程日记 2025/8/12 10:58:12

算法题（100）：腐烂的苹果

审题： 本题需要我们判断苹果是否可以完全腐烂，若可以完全腐烂，那么最短腐烂的所需时间是多少思路： 方法一：多源BFS 首先我们分析腐烂过程，第一批腐烂苹果开始扩散，然后第二批腐烂苹果继续扩散&…...

编程日记 2025/8/12 2:11:54

1、必要库的载入 import pandas as pd import matplotlib.pyplot as plt import seaborn as sns2、加载并清洗数据 # 2.1 加载数据 df pd.read_csv(/home/mw/input/survey6263/mcdonalds.csv)# 2.2 数据清洗 # 2.2.1 检查缺失值 print(缺失值情况：) print(df.isn…...

编程日记 2025/8/8 11:33:29

【微服务】如何用Azure容器应用Job处理异步HTTP API请求

【微服务】如何用Azure容器应用Job处理异步HTTP API请求推荐超级课程：本地离线DeepSeek AI方案部署实战教程【完全版】Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战目录【微服务】如何用Azure容器应用Job处理异步HTTP API请求Azure容器应用中的长…...

编程日记 2025/8/8 10:53:21

安卓edge://inspect 和 chrome://inspect调试移动设备上的网页

edge://inspect 和 chrome://inspect 是用于调试浏览器中运行的网页和移动设备上的网页的工具。这两个工具分别属于 Microsoft Edge 和 Google Chrome 浏览器。以下是它们的详细介绍： chrome://inspect 如果是直接使用数据线调试，则只需要执行下面的第一…...

编程日记 2025/8/7 23:28:13

TX-LCN 框架

TX-LCN 框架通俗教学（面试场景版） 一句话概括 TX-LCN 是分布式事务的 “交通警察”，确保多个微服务操作要么全部成功（比如转账扣款和到账），要么全部回滚（比如网购下单失败后库存自动恢复&#…...

编程日记 2025/8/12 10:58:12

玩转github

me github 可以给仓库添加开发人员吗 4o 是的，GitHub允许仓库管理员为仓库添加开发人员，并设置这些开发人员的角色和权限。这里是一个简单的步骤指导，教你如何给一个 GitHub 仓库添加开发人员： 前提条件你必须有这个仓库的权限&…...

编程日记 2025/7/2 3:42:56

Dubbo 深度解析

Dubbo 深度解析与实战指南一、Dubbo 核心设计理念与应用场景 1.1 为什么需要 Dubbo？ 随着互联网业务规模扩大，单体架构面临以下挑战： 服务依赖复杂：模块间耦合度高，难以独立迭代[[5]]。性能瓶颈：单一应…...

编程日记 2025/8/11 5:59:54

基于javaweb的SpringBoot校园运动会管理系统设计与实现(源码+文档+部署讲解）

技术范围：SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。主要内容：免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论…...

编程日记 2025/8/11 2:54:54

Socket封装---模板方法类

目录一、模板方法类二、Socket的框架三、TCPSocket对父类的虚函数重写在平时写网络代码的时候，经常会涉及到socket套接字的部分，这一部分用的十分频繁，但是流程都是固定的，我实在是饱受其苦，但是由于C不像java一…...

编程日记 2025/8/2 16:20:32

牛客周赛84 题解 Java ABCDEFG AK实录

目录题目地址做题情况 A 题 B 题 C / D 题 E 题 F / G 题题目地址牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ 做题情况 A 题 import java.io.*; import java.math.*; import java.util.*;// xixi♡西 public class Main {static IOS scnew…...

编程日记 2025/8/8 21:15:10

如何使用MySQL快速定位慢SQL问题？企业级开发中常见业务场景中实际发生的例子，涉及分页查询问题。（二）

如何使用MySQL快速定位慢SQL问题？ 在企业级开发中，尤其是涉及到订单查询的业务时，经常会发生慢查询的问题。比如用户翻页到后面的页数时，查询变慢，因为传统的LIMIT offset, size在数据量大时效率低下。这时候&#xff…...

编程日记 2025/8/9 18:12:59

双链笔记新选择！使用Docker私有化部署Logseq知识库远程团队协作

前言：嘿，小伙伴们，今天要给大家安利一个超酷的技能——如何在本地Linux服务器上使用Docker轻松搭建Logseq笔记软件，并通过cpolar内网穿透工具实现远程访问。大家都知道，在快节奏的工作和学习中，一个好的笔记…...

编程日记 2025/8/11 7:28:34

C# 不同框架如何调用framework 和 net core

在 C# 中实现进程间通信（IPC，Inter-Process Communication）有多种方式，适用于不同场景。以下是常见 IPC 方法的实现方案、代码示例及适用场景对比： 1. 命名管道（Named Pipes） 特点：…...

编程日记 2025/8/7 22:17:03

【Linux-传输层协议TCP】TCP协议段格式+确认应答+超时重传+连接管理机制（三次握手、四次挥手、理解TIME_WAIT + CLOSE_WAIT）

TCP协议 TCP全称为“传输控制协议（Transmission Control Protocol）”人如其名，要对数据的传输进行一个详细的控制。 1.TCP协议段格式下面是TCP报头各个字段的表格形式： 字段名称字段大小描述源端口16位发送端TCP端口号。目的端…...

编程日记 2025/8/11 3:02:09

怎样使用Modbus转Profinet网关连接USB转485模拟从站配置案例

怎样使用Modbus转Profinet网关连接USB转485模拟从站配置案例 Modbus转profinet网关可以将Modbus协议转化为profinet协议，以实现设备之间的数据交互。在实际使用过程中，我们需要使用Modbus协议进行设备通讯，而profinet协议则是用于工业自动化…...

编程日记 2025/8/5 17:54:39

从“自习室令牌”到线程同步：探秘锁与条件变量

目录互斥为什么需要锁锁的原理--互斥锁的使用同步锁的问题条件变量互斥为什么需要锁先看结果： 以下代码是我模拟创建线程抢票，由于不加锁导致票抢到了负数 main.cc: #include<vector> #include<iostream> #include"…...

编程日记 2025/8/12 5:11:04

Java 大视界 -- Java 大数据在智能政务舆情引导与公共危机管理中的应用（138）

💖亲爱的朋友们，热烈欢迎来到青云交的博客！能与诸位在此相逢，我倍感荣幸。在这飞速更迭的时代，我们都渴望一方心灵净土，而我的博客正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识，也…...

编程日记 2025/8/11 22:16:59

LeetCode[59]螺旋矩阵Ⅱ

思路： 这种题我第一次确实没做出来，第一次做的时候一圈一圈处理，发现圈数越往里，越乱，原来之前是没从圈数开始遍历。思路：第一个大循环先遍历圈数，一共遍历n/2圈，如果是奇数那就最后…...

编程日记 2025/8/9 1:21:59

【Python 算法 1.线性枚举】

我装作漠视一切，以为这样就可以不在乎 —— 25.3.17 一、线性枚举的基本概念 1.时间复杂度线性枚举的时间复杂度为 O(nm)，其中 n是线性表的长度。m 是每次操作的量级，对于求最大值和求和来说，因为操作比较简单，所以 …...

编程日记 2025/8/6 16:30:32

C# 嵌套类详解

一个类在它的包容类外没有多大意义，就适合设计成嵌套类。嵌套类：定义在另一个类内部的类。包容类（外部类）：包含嵌套类的类。嵌套类的独特之处是可以为类自身指定private访问修饰符。嵌套类能访问包容类的任何成…...

编程日记 2025/8/1 18:08:01

深度学习中学习率调整策略

学习率衰减策略是深度学习优化过程中的一个关键因素，它决定了训练过程中学习率的调整方式，从而影响模型收敛的速度和效果。不同的衰减策略在不同的任务和模型上可能有不同的表现，下面从我用到过的几个衰减策略进行记录，后续慢慢跟…...

编程日记 2025/8/11 0:47:48

基于Flask的东方财富网股票数据可视化分析系统

【大数据】基于Flask的东方财富网股票数据可视化分析系统 （完整系统源码开发笔记详细部署教程）✅ 目录一、项目简介二、项目界面展示三、项目视频展示一、项目简介该系统能够高效地从东方财富网抓取股票数据，并通过Python的强大数据处理能…...

编程日记 2025/8/10 13:20:23

卓越的用户体验需要智能内容

摘要：这篇文章指出静态文档已无法满足现代用户的需求，而智能内容则是构建卓越用户体验的关键。文章从智能内容的定义、优势和实际应用等方面进行了详细阐述，并强调了企业应积极拥抱智能内容，以提升客户满意度、降低成本并创造新的…...

编程日记 2025/8/8 23:03:11

c++基础知识-图论进阶

一、拓扑排序 1、基础知识 1）什么是拓扑排序对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若，则u在线性序列中出现在v之前。 2）拓扑排序的操作方法重复执行…...

编程日记 2025/8/3 3:42:12

Java 买百鸡问题

二阶买百鸡问题：母鸡5元一只，公鸡3元一只，35元可以有多少种买法刚好用完？ package com.software.first;import java.util.Scanner;public class Test {public static void main(String[] args) {Scanner scan new Scanner(Syste…...

编程日记 2025/8/1 13:37:47

为什么手机上用 mA 和 mAh 来表示功耗和能耗？

在手机上，我们经常会看到 mA（毫安） 和 mAh（毫安时） 这两个单位，它们分别用来表示功耗水平和能耗水平。为什么用这两个单位呢？其实这和电流、时间以及电池的特性有关。 1.mA（毫安…...

编程日记 2025/8/6 9:12:41

使用SDKMAN!安装springboot

在 Ubuntu 环境中使用 sdk install springboot 命令之前，您需要先安装 SDKMAN!（Software Development Kit Manager）。以下是详细的安装步骤： 安装 SDKMAN! 打开终端。运行以下命令以安装 SDKMAN!： curl -s "htt…...

编程日记 2025/8/9 6:46:39

【AI学习从零至壹】Pytorch神经⽹络

Pytorch神经⽹络神经网络简介神经元激活函数神经网络神经⽹络的⼯作过程前向传播(forward) 反向传播(backward)训练神经⽹络 Pytorch搭建并训练神经⽹络神经⽹络构建和训练过程数据预处理构建模型优化器&提取训练数据训练样本神经网络简介神经元在深度学习中&#x…...

编程日记 2025/8/7 13:43:55

Linux应用 / 驱动程序崩溃调试

文章目录前言一、GDB 使用1. GDB 介绍2. Debug版本与Release版本3. 指令演示3.1 显示行号3.2 断点设置3.3 查看断点信息3.4 删除断点3.5 开启 / 禁用断点3.6 运行3.7 打印 / 追踪变量 4. 最常用指令二、Linux 应用程序调试1. codedump 介绍2. 在 Linux 系统中使用 coredump2.…...

编程日记 2025/8/12 1:24:31