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

C++位运算精要：高效解题的利器

news 来源：原创 2025/7/3 1:11:53

引言

在算法竞赛和底层开发中，位运算（Bit Manipulation）因其极高的执行效率而广受青睐。它能在O(1)时间复杂度内完成某些复杂操作，大幅优化程序性能。本文系统梳理C++位运算的核心技巧，涵盖基础操作、经典应用、优化策略及实战例题，帮助读者掌握这一高效工具。

一、位运算基础

1. 六大基本操作

运算符	名称	示例（二进制）	说明
`&`	按位与	`1010 & 1100 = 1000`	同1为1，否则为0
`\|`	按位或	1010\|1100 = 1110	有1则1，全0为0
`^`	按位异或	`1010 ^ 1100 = 0110`	不同为1，相同为0
`~`	按位取反	`~1010 = 0101`（4位）	0变1，1变0
`<<`	左移	`0011 << 2 = 1100`	低位补0，相当于×2ⁿ
`>>`	右移	`1100 >> 2 = 0011`	高位补符号位（算术右移）

2. 常用位运算性质

异或（XOR）特性：
- a ^ a = 0，a ^ 0 = a
- 交换律：a ^ b = b ^ a
- 结合律：(a ^ b) ^ c = a ^ (b ^ c)
与（AND）和或（OR）的分配律：
- a & (b | c) = (a & b) | (a & c)
- a | (b & c) = (a | b) & (a | c)

二、位运算实战技巧

1. 判断奇偶

bool isOdd(int n) {return n & 1; // 奇数返回true
}

原理：二进制末位为1表示奇数。

2. 交换两个数（无需临时变量）

void swap(int &a, int &b) {a ^= b;b ^= a;a ^= b;
}

注意：若a和b指向同一内存，此方法会失效。

3. 取绝对值

int abs(int n) {int mask = n >> (sizeof(int) * 8 - 1); // 符号位扩展return (n ^ mask) - mask;
}

适用场景：嵌入式设备等无分支优化需求。

4. 检查是否为2的幂

bool isPowerOfTwo(int n) {return n > 0 && (n & (n - 1)) == 0;
}

原理：2ⁿ的二进制形式为100...0，n & (n-1)会消除唯一的1。

5. 统计二进制中1的个数（Brian Kernighan算法）

int countOnes(int n) {int count = 0;while (n) {n &= (n - 1); // 每次消除最右边的1count++;}return count;
}

时间复杂度：O(k)，k为1的个数。

6. 最低位的1

int lowBit(int x) {return x & (-x);
}

应用：树状数组（Fenwick Tree）的核心操作。

7. 模拟集合操作

表示集合：用整数二进制位表示元素是否存在（如mask = 5（101）表示包含第0和第2个元素）。

常用操作：

int S = 0b1010;          // 集合{1, 3}
S |= (1 << 2);           // 添加元素2 → S = 0b1110
S &= ~(1 << 1);          // 删除元素1 → S = 0b1100
bool has = S & (1 << 3); // 检查元素3是否存在

三、位运算优化策略

1. 替代乘除法

左移1位等价于×2：
```
int a = 5;
a <<= 1; // a = 10
```
右移1位等价于÷2（向下取整）：
```
int b = 7;
b >>= 1; // b = 3
```

2. 状态压缩DP

问题示例：旅行商问题（TSP）中，用二进制数表示访问过的城市。

int dp[1 << n][n]; // dp[mask][i]表示从城市i出发，访问过mask集合的最短路径
for (int mask = 0; mask < (1 << n); mask++) {for (int i = 0; i < n; i++) {if (mask & (1 << i)) {// 状态转移}}
}

3. 快速幂算法

int fastPow(int a, int b) {int res = 1;while (b) {if (b & 1) res *= a;a *= a;b >>= 1;}return res;
}

时间复杂度：O(log b)。

四、经典例题解析

例题1：只出现一次的数字（LeetCode 136）

问题：数组中只有一个数出现一次，其余均出现两次，找出该数。
解法：

int singleNumber(vector<int>& nums) {int res = 0;for (int num : nums) res ^= num;return res;
}

关键点：利用a ^ a = 0的性质。

例题2：位1的个数（LeetCode 191）

问题：统计无符号整数的二进制表示中1的个数。
解法：

int hammingWeight(uint32_t n) {int count = 0;while (n) {n &= (n - 1);count++;}return count;
}

例题3：子集生成（LeetCode 78）

问题：给定无重复元素的数组，返回所有子集。
位运算解法：

vector<vector<int>> subsets(vector<int>& nums) {int n = nums.size();vector<vector<int>> res;for (int mask = 0; mask < (1 << n); mask++) {vector<int> subset;for (int i = 0; i < n; i++) {if (mask & (1 << i)) subset.push_back(nums[i]);}res.push_back(subset);}return res;
}

五、总结

位运算通过直接操作二进制位，能够实现：

高效数学运算（如乘除、取模）；
状态压缩（优化DP、集合操作）；
算法优化（快速幂、Brian Kernighan算法）。

掌握位运算，不仅能提升代码性能，还能在面试和竞赛中脱颖而出。建议通过LeetCode相关题目（如268、371、201）加强练习。

C++位运算精要：高效解题的利器

引言在算法竞赛和底层开发中，位运算（Bit Manipulation）因其极高的执行效率而广受青睐。它能在O(1)时间复杂度内完成某些复杂操作，大幅优化程序性能。本文系统梳理C位运算的核心技巧，涵盖基础操作、经典应用、优化策略…...

编程日记 2025/7/3 1:11:53

从前序与中序遍历序列构造二叉树题目描述代码实现 class Solution { private:unordered_map<int, int> mapIn;TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_right){//出口if(…...

编程日记 2025/7/2 23:24:29

【C语言】字符函数的易错点及其模拟实现

在上一章为大家简单介绍了字符函数的种类和基础运用，语法。那么在本章为大家分享一些易错点和自己如何编写一个自定义函数来实现相同的作用。（点个关注呗） 一strlen：计算字符串长度 1. 函数原型 size_t strlen(const char *str…...

编程日记 2025/7/3 16:58:23

【前端】创建一个vue3+JavaScript项目流程

1、检查node和npm是否安装，查看版本： node -v npm -v 2、安装脚手架cli或vite （1）cli 安装：npm install -g vue/cli 检查是否安装成功：vue -v 使用cli创建项目：vue create my-project(项目名)--…...

编程日记 2025/7/3 17:04:15

JVM面试专题

目录 1 JVM组成 1.1 JVM由那些部分组成，运行流程是什么？ 1.2 什么是程序计数器？ 1.3 你能给我详细的介绍Java堆吗? 元空间(MetaSpace)介绍 1.4 什么是虚拟机栈 1.5 方法区 1.5.1 概述 1.5.2 常量池 1.5.3 运行时常量池 1.6 你听过…...

编程日记 2025/7/3 16:44:06

齐次线性方程组及python求解

齐次线性方程组的概念齐次线性方程组是指所有常数项都为零的线性方程组，其一般形式为： a 11 x 1 a 12 x 2 ⋯ a 1 n x n 0 a_{11}x_1 a_{12}x_2 \cdots a_{1n}x_n 0 a11x1a12x2⋯a1nxn0 a 21 x 1 a 22 x 2 ⋯ a 2 n x n 0 a_…...

编程日记 2025/7/3 15:25:14

鸿蒙前后端项目源码-点餐v3.0-原创!原创!原创!

鸿蒙前后端点餐项目源码含文档ArkTS语言. 原创作品.我半个月写的原创作品，请尊重原创。原创作品，盗版必究！！！！ 原创作品，盗版必究！！！！ 原创作…...

编程日记 2025/7/3 1:09:17

【数据结构】算法效率的双刃剑：时间复杂度与空间复杂度

前言在算法的世界里，效率是衡量算法优劣的关键标准。今天，就让我们深入探讨算法效率的两个核心维度：时间复杂度和空间复杂度，帮助你在算法设计的道路上更进一步。一、算法效率：衡量算法好坏的关键算法的效率主要…...

编程日记 2025/7/3 1:16:42

Linux | I.MX6ULL 终结者底板原理图讲解(5)

01 USB 转串口电路 I.MX6ULL 终结者开发板板载了一个 USB 串口，原理图如图 1 和图 2 所示： USB 转串口我们使用的是 CH340G 芯片，该芯片是由南京沁恒微电子研发生产的一款国产芯片。CH340G的工作电压支持 3.3V、5V，甚至是 3V，从上图可以看到我们给 CH340G 的电压是 5V…...

编程日记 2025/7/3 4:22:08

java拆分字符串、去重并统计相关长度

java拆分字符串、去重并统计相关长度 20250331 19:52 求取逗号隔开的字符串的的长度，要求去重。拆分字符串应该是指按照某种分隔符将字符串分割成多个部分，然后去除重复的部分，最后统计处理后各个部分的长度或者总长度。这时候可能需要明确…...

编程日记 2025/7/3 15:13:57

Vue 2 和 Vue 3 有什么区别

Vue 2 和 Vue 3 是 Vue.js 框架的两个主要版本，它们在核心特性、性能、API 设计等方面有一些显著的区别。以下是它们的主要区别： 1. 核心特性 • Composition API： • Vue 3 引入了 Composition API，这是一种新的 API&#xff0…...

编程日记 2025/7/3 16:03:20

RabbitMQ、RocketMQ 和 Kafka 的消息特性对比

以下是 RabbitMQ、RocketMQ 和 Kafka 在保证消息不丢失、消息顺序、消息幂等性以及快速处理积压方面的详细对比： 1. 消息不丢失特性RabbitMQRocketMQKafka生产者端开启事务或 Confirm 模式使用事务消息机制设置 acksall 确保消息被所有副本确认服务端消息持久化&…...

编程日记 2025/6/29 10:55:37

Logback 实现不同包的日志记录到不同文件

核心通过合理配置多个 appender 来定义不同的日志输出目的地通过 logger 元素将不同的包与对应的 appender 关联起来同时利用 additivity 属性控制日志的传递，从而实现精准的日志输出管理。 additivity 属性控制日志传递： additivity 属性决定了该 l…...

编程日记 2025/7/2 19:13:01

【附JS、Python、C++题解】Leetcode面试150题（11）H指数

一、题目 274. H 指数给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数是指他&#xf…...

编程日记 2025/7/2 4:20:28

C++第13届蓝桥杯省b组习题笔记

1.九进制转十进制九进制正整数 (2022)9转换成十进制等于多少？ 第一位乘9的0次方，第二位乘9的1次方，第三位乘9的二次方以此类推 #include <iostream> using namespace std;int main() {// 请在此输入您的代码int t2022;int res0;int c…...

编程日记 2025/6/30 10:26:42

【学Rust写CAD】19 颜色渐变定义（gradient_stop.rs）

源码 //color/gradient_stop.rs use super::argb::Color; #[derive(Clone, Copy, Debug)] pub struct GradientStop {pub position: f32,pub color: Color, }代码分析这段代码是一个结构体（struct），并为其派生（derive&#xff…...

编程日记 2025/7/3 8:57:57

从零开始跑通3DGS教程：介绍

写在前面本文内容本文所属《从零开始跑通3DGS教程》系列文章，将实现从原始图像(有序、无序)数据开始，经过处理(视频抽帧成有序)，SFM，3DGS训练、编辑、渲染等步骤，完整地呈现从原始图像到新视角合成的全部流程&#x…...

编程日记 2025/7/3 20:05:47

探索 Python 编程的宇宙：从基础到进阶的奇妙之旅

在当今的编程世界里，Python 以其简洁、易读和强大的功能，成为了众多开发者的心头好。它就像一个充满无限可能的宇宙，吸引着人们不断去探索其中的奥秘。今天，让我们一起踏上这场 Python 编程的奇妙之旅，从基础到进阶&am…...

编程日记 2025/6/30 7:08:41

使用 Spring AI 和 LangChain4j 实现聊天机器人对比分析

人工智能领域正在彻底改变公司管理客户服务的方式。随着 Spring AI 和 LangChain4j 等专用框架的出现，Java 开发人员现在拥有强大的工具来实现能够从公司数据中学习的智能聊天机器人。在本文中，我们将探讨这两个框架的主要功能，并了解如何使用…...

编程日记 2025/7/3 4:13:02

3月31（信息差）

1.全国首个！湖北为脑机接口医疗服务定价据湖北省医疗保障局消息，今日，湖北省医保局发布全国首个脑机接口医疗服务价格，其中，侵入式脑机接口植入费6552 元/次，侵入式脑机接口取出费3139元/次，非侵入式脑机接口适配费966元/次，标志着这一前沿科技正式步入民生领域，为无…...

编程日记 2025/6/28 4:28:52

苍穹外卖项目结构

苍穹外卖项目总结-CSDN博客【苍穹外卖|项目】万字总结-CSDN博客苍穹外卖项目总结_苍芎外卖如何实现的跨域-CSDN博客【苍穹外卖 | 项目日记】第九天万字总结-CSDN博客【苍穹外卖|项目】万字总结-CSDN博客一、技术点： Nginx代理负载均衡：通过…...

编程日记 2025/7/2 7:53:03

3. 无重复字符的最长子串

leetcode Hot 100系列文章目录一、核心操作二、外层配合操作三、核心模式代码总结一、核心操作用map，key为char，value为出现次数，将字符串中的值依次入栈，再判断次数是否大于1，如果大于1，则循环删除掉…...

编程日记 2025/7/1 18:30:45

python力扣48.旋转图像

给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例 1： 输入：matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&…...

编程日记 2025/7/3 6:55:55

文章配图新纪元：OpenAI新推出的GPT-4o原生图像生成功能启示

当OpenAI推出GPT-4o原生图像生成功能时，许多人惊呼：“AI生成的图像已经发展到这样了吗！”这一激动人心的时刻，标志着人工智能在图像创作领域迈出了历史性的一步。无论是细腻的人物肖像，栩栩如生的面部表情，…...

编程日记 2025/6/30 8:06:35

使用Google Gemini API密钥创建AI驱动的Chrome扩展程序

在这个快节奏的数字时代，我们高度依赖Chrome扩展程序来提升浏览效率。但你是否想过用人工智能为你的扩展注入超能力？听起来很酷对吧？😎 随着谷歌Gemini API的发布，AI技术变得触手可及。该API能让你在项目中直接调用先进的自然语言处理、图像识别等炫酷的AI功能。更…...

编程日记 2025/6/29 7:49:21

MapReduce的工作原理

MapReduce 是 Hadoop 的核心计算框架，用于分布式处理大规模数据集。它的核心思想是 **"分而治之"**，将任务拆分为多个子任务并行处理，最终汇总结果。以下是其工作原理的详细解析 1. 核心阶段 MapReduce 的执行过程分为三个阶段&a…...

编程日记 2025/6/28 1:25:02

k8s网络策略

k8s网络策略 k8s网络测试概述查看防火墙策略 k8s网络策略网络访问控制案例：配置k8s网络策略结果验证 k8s网络策略配置示例 k8s网络测试概述网络策略就是设置防火墙查看防火墙策略 # 获取当前命名空间下的所有 NetworkPolicy 资源（网络策略&#xff0…...

编程日记 2025/7/2 13:16:47

Linux文件描述符的分配机制与重定向实现：揭开“一切皆文件”的面纱

Linux系列文章目录 Linux系列前言一、Linux的标准流二、文件描述符分配规则三、文件重定向四、Linux下一切皆文件前言上篇我们介绍了语言和系统层次的基础I/O文件操作，其涉及的知识有：C语言文件操作和系统调用接口两者的关系、文件描述符的概念、操作…...

编程日记 2025/6/29 5:50:34

SpringBoot事务管理（四）

记录几条SpringBoot事务管理中踩过的坑及解决办法： 1. 自调用问题问题描述在同一个类中，一个非事务方法调用另一个有 Transactional 注解的事务方法，事务不会生效。因为 Spring 的事务管理是基于 AOP 代理实现的，自调用时不会…...

编程日记 2025/7/3 7:02:13

iOS GCD

GCD 任务队列主队列： 任务在主线程执行，主队列是一个串行队列，它主要处理 UI 相关任务，也可以处理其他类型任务，但为了性能考虑，尽量让主队列执行 UI 相关或少量不耗时间和资源的操作。系统全局并发队…...

编程日记 2025/6/27 18:05:37

Hadoop集群的常用命令

1.基本命令启动 Hadoop: start-dfs.sh start-yarn.sh 这些命令会分别启动 Hadoop 的 DFS 和 YARN。查看 Hadoop 目录: hdfs dfs -ls -R / 该命令会递归地列出 HDFS 根目录下的所有文件和目录。创建目录: hdfs dfs -mkdir /example_dir 在 HDFS 中创建一个新目录。上传文…...

编程日记 2025/6/28 1:25:09

Kafka 实战指南：原理剖析与高并发场景设计模式

一、介绍 Kafka是由 Apache 软件基金会开发的开源流处理平台，作为高吞吐量的分布式发布订阅消息系统，采用 Scala 和 Java 编写。 Kafka是一种消息服务（MQ），在理论上可以达到十万的并发。代表的MQ软件—— kafka 十万…...

编程日记 2025/6/28 1:25:11

黑盒测试的判定表法（能对多条件依赖关系进行设计测试点）

定义: 判定表是分析和表达多逻辑条件下执行不同操作的工具。就是指把所有的输入条件、所有可能采取的动作按表格列出来，每一种条件和动作的组合构成一条规则，也即一条用例。 1.判定表法的引用等价类边界值分析法主要关注单个输入类条件的测试并未考虑…...

编程日记 2025/6/27 21:07:34

SQLMesh系列教程：基于指标构建一致的分析语义层应用实践

本文深入探讨SQLMesh指标框架的核心概念、定义方法及应用场景。通过统一的语义层管理，SQLMesh解决了数据分析中指标定义不一致的痛点，实现了跨团队协作的数据一致性。文章包含指标定义语法详解、自动表连接机制解析、派生指标构建方法，并通过…...

编程日记 2025/7/1 12:23:07

解决Docker端口映射后外网无法访问的问题

一、前言今天因为服务器宕机，重新启动后发现docker部署的mysql和redis都无法通过外网访问。经过排查原因是ip转发没有开启。下面教大家如何解决二、问题排查 (1) 查看防火墙运行情况使用firewall-cmd --state 如果防火墙处于not running，则可以排…...

编程日记 2025/6/28 5:05:17

如何指定运行amd64架构的ubuntu？

如何指定运行amd64架构的ubuntu 下面这个命令如何制定运行amd64架构的ubuntu？ docker run -it -v $(pwd):/workspace ubuntu:20.04 bash这个命令已经非常接近正确运行一个基于 amd64 架构的 Ubuntu 容器了，但如果你想明确指定运行 amd64 架构的镜像&am…...

编程日记 2025/6/27 9:02:14

[MySQL]数据类型

数据类型 1.数据类型分类2.数值类型2.1 tinyint类型无符号类型举例 3.bit类型3.1 基本语法 4. 小数类型4.1 float语法4.2 decimal语法 5.字符串类型5.1 char类型5.2 varchar 6.日期类型7.enum和set查询语句 1.数据类型分类接下来就对上面的四种类型进行介绍 2.数值类型数值类…...

编程日记 2025/6/28 6:41:08

基于Python的Django框架的手机购物商城管理系统

标题:基于Python的Django框架的手机购物商城管理系统内容:1.摘要随着互联网的快速发展，手机购物逐渐成为人们日常生活中不可或缺的一部分。本研究的目的是开发一个基于Python的Django框架的手机购物商城管理系统，以提高购物商城的管理效率和用户体验。…...

编程日记 2025/7/2 11:32:59

大模型在2型糖尿病预测及围手术期管理中的应用研究

目录一、引言 1.1 研究背景与意义 1.2 国内外研究现状 1.3 研究目的与创新点二、大模型预测 2 型糖尿病的原理与方法 2.1 大模型概述 2.2 用于 2 型糖尿病预测的大模型类型 2.3 模型训练与数据来源 2.4 预测指标与算法三、术前风险预测与评估 3.1 血糖控制情况预…...

编程日记 2025/7/3 4:25:10

JavaEE--多线程

一、认识线程 1. 什么是线程线程（Thread）是计算机科学中的基本概念，指的是程序内部的一条执行路径。一个进程可以包含多个线程，每个线程共享进程的资源，包括内存空间、文件描述符等。线程可以同时执行多个任务&…...

编程日记 2025/6/28 4:06:31

自动化测试之等待方式

在自动化测试中，等待是一个重要的技术，用于处理页面加载、元素定位、元素状态改变等延迟问题。等待能够确保在条件满足后再进行后续操作，提高自动化测试的稳定性以及可靠性。等待方式：显示等待、隐式等待、线程睡眠 1. 显式等…...

编程日记 2025/7/1 1:18:19

git中用于生成commitId与其父commitId间的文件差异文件树

生成commitId与其父commitId间的文件差异文件树 #!/bin/bash # # 用于生成目标commitId与其父commitId间文件差异 # commit_id$1 # 输入目标commit的哈希值 old_dir"old_version" new_dir"new_version"# 创建目录 mkdir -p "$old_dir" "$…...

编程日记 2025/6/28 5:07:28

Ubuntu / Debian 创建快捷方式启动提权

简述在 Linux 系统中，.desktop 文件是桌面入口文件，用于在桌面环境（如 GNOME、KDE）中定义应用程序的启动方式、图标、名称等信息。当你执行 touch idea.desktop 时，实际上创建了一个空的 .desktop 文件（…...

编程日记 2025/6/30 9:41:55

VLA 论文精读（三）Diffusion Policy: Visuomotor Policy Learning via Action Diffusion

这篇笔记用来描述 2023年发表在arxiv上的一篇有关VLA领域的论文，这篇笔记记录的是该论文 2024年03月的改版后。写在最前面为了方便你的阅读，以下几点的注意事项请务必了解： 该系列文章每个字都是我理解后自行翻译并写上去的，…...

编程日记 2025/7/2 21:48:41

ASP.NET Core 中实现 SSE 流式响应的简单例子

[HttpGet] public async Task<IActionResult> SseExample() {// 请求头Response.Headers.Add("Content-Type", "text/event-stream");Response.Headers.Add("Cache-Control", "no-cache");Response.Headers.Add("Connectio…...

编程日记 2025/7/1 7:35:39

「Unity3D」TMP_InputField关闭虚拟键盘后，再次打开虚拟键盘，此时无法回调onSelect的问题

TMP_InputField可以注册一个onSelect回调函数，在InputField选中的时候回调，但在虚拟键盘手动关闭或被返回取消的时候，此时再打开虚拟键盘时，就不会调用onSelect。原因在于，虚拟键盘有三种关闭的操作方式：…...

编程日记 2025/7/2 19:27:49

手工排查后门木马的常用姿势

声明！本文章所有的工具分享仅仅只是供大家学习交流为主，切勿用于非法用途，如有任何触犯法律的行为，均与本人及团队无关！！！ 1. 检查异常文件 （1）查找最近修改的文件 # 查…...

编程日记 2025/7/2 15:46:16

VRRP协议

基础概念 Master 路由器:“Master 路由器”在一个 VRRP 组中承担报文转发任务。在每一个 VRRP 组中，只有 Master 路由器才会响应针对虚拟 IP 地址的 ARP Request。Master 路由器会以一定的时间间隔周期性地发送 VRRP 报文，以便通知同一个 VRRP 组中的 B…...

编程日记 2025/6/29 19:09:04

【JavaEE】MyBatis 综合练习（图书管理系统）

目录一、数据库表二、引入依赖：三、Model创建四、用户登录五、添加图书六、图书列表七、修改图书八、删除图书九、批量删除十、强制登录图书管理系统一、数据库表我们使用两张表，一张用户表uset_test来记录登录的用户信息，一张图书表boo…...

编程日记 2025/7/2 1:21:10

ArkUI —— 组件导航

创建导航页 // src\main\ets\pages\Index.ets Entry Component struct Index {// 路由栈Provide(pathInfos) pathInfos: NavPathStack new NavPathStack()build() {Navigation(this.pathInfos) {}} }创建导航子页 this.navPath.pushPathByName(AccountTag, 账本分类管理)// …...

编程日记 2025/6/28 1:58:47

引言