算法——位运算

1. 基础位运算

位运算符是在二进制位级别上对数据进行操作的运算符。以下是一些常见的位运算符:

1. 右移运算符 (>>)

将一个数的所有二进制位向右移动指定的位数。右移运算符 >> 表示将运算符左边的操作数的所有位向右移动右边指定的位数,右边多余的位将被丢弃,左边用符号位填充。

int x = 8;  // 二进制: 0000 1000
int result = x >> 2;  // 二进制: 0000 0010,即十进制的 2

2. 左移运算符 (<<)

将一个数的所有二进制位向左移动指定的位数。左移运算符 << 表示将运算符左边的操作数的所有位向左移动右边指定的位数,左边多余的位将被丢弃,右边用零填充。

int x = 8;  // 二进制: 0000 1000
int result = x << 2;  // 二进制: 0010 0000,即十进制的 32

3. 按位取反运算符 (~)

对一个数的每个二进制位执行取反操作,即将 0 变为 1,将 1 变为 0。

int x = 5;  // 二进制: 0000 0101
int result = ~x;  // 二进制: 1111 1010,即十进制的 -6

4. 按位或运算符 (|)

对两个数的每个二进制位执行按位或操作,只要有一个为 1,结果位就为 1。

int x = 5;  // 二进制: 0000 0101
int y = 3;  // 二进制: 0000 0011
int result = x | y;  // 二进制: 0000 0111,即十进制的 7

5. 按位与运算符 (&)

对两个数的每个二进制位执行按位与操作,只有两个都为 1,结果位才为 1。

int x = 5;  // 二进制: 0000 0101
int y = 3;  // 二进制: 0000 0011
int result = x & y;  // 二进制: 0000 0001,即十进制的 1

6. 按位异或运算符 (^)

对两个数的每个二进制位执行按位异或操作,如果两个位不同则结果位为 1,相同则为 0。或者可以简单记忆为无进位相加。

int x = 5;  // 二进制: 0000 0101
int y = 3;  // 二进制: 0000 0011
int result = x ^ y;  // 二进制: 0000 0110,即十进制的 6

2. 位图

位图(Bitmap)是一种用于表示二进制数据的数据结构,通常用于表示一组二进制位的状态。它的核心思想是用二进制位的值(0或1)来表示某种状态或信息。它的主要核心操作即以下三步

1. 给定一个数n,确定它的二进制表示中的第x位是0还是1

要想判断某一个位置是0还是1只需要对这个位置&上一个1,如果该位置为1则结果为1,反之则结果为0,在这里我们要想快速判断可以使用

(n >> x) & 1

2. 将一个数n的二进制表示的第x位修改成1

要想修改x位置的值为1,只需要对这个位置|上一个1,其余位置|上0,这样就可以将该位置修改成1,即

在这里我们要想快速修改可以使用

(1 << x) | n

3. 将一个数n的二进制表示的第x位修改成0

 要想修改x位置的值为0,只需要对这个位置&上一个0,其余位置&上1,这样就可以将该位置修改成0,即

在这里我们要想快速修改可以使用

(~(1 << x)) & n

4. 位图的思想 

从使用上来说,位图其实与哈希表相似只不过哈希表是创建一个数组来存储信息,而位图则是使用比特位中的0与1来存储信息。

3. 提取与删除二进制中最右侧的1

1. 提取(lowbit)

要想提取最右侧的0,只需要让n & -n,即

可以看到,这个操作的本质就是将最右侧的1的左边区域全部变为相反的数

2. 删除

要想提取最右侧的0,只需要让n & (n - 1),即

可以看到,这个操作的本质是将最右侧的1的右边区域(包含1)全部变为相反数

4. 异或运算(^)的运算律

异或运算律如下

1. a ^ 0 = a

2. a ^ a = 0

3. a ^ (b ^ c) = (a ^ b) ^ c

5. 应用实例

1. 位1的个数

题目链接:191. 位1的个数 - 力扣(LeetCode)

解析:根据题意我们可以使用删除最右侧的1操作来统计个数,代码如下

class Solution 
{
public:int hammingWeight(uint32_t n) {int num = 0;while (n){num++;n &= (n - 1);}    return num;}
};

2. 比特位计数

题目链接:338. 比特位计数 - 力扣(LeetCode)

解析:这道题也可以使用删除最右侧的1策略来统计,代码如下

class Solution 
{
public:vector<int> countBits(int n) {vector<int> ret;for (int i = 0; i <= n; i++){int num = 0, cur = i;while (cur){num++;cur &= (cur - 1);}ret.push_back(num);}return ret;}
};

3. 汉明距离

题目链接:461. 汉明距离 - 力扣(LeetCode)

解析:这里我们需要求得不同的二进制位个数,由于异或操作可以达到相异为1,相同为0的效果,我们只需要将两个数异或并统计异或后1的数量即可,代码如下

class Solution 
{
public:int hammingDistance(int x, int y) {int ret = 0;int tmp = x ^ y;while (tmp){ret++;tmp &= (tmp - 1);}return ret;}
};

4. 只出现一次的数字

题目链接:136. 只出现一次的数字 - 力扣(LeetCode)

解析:这道题我们可以利用异或的性质,由于只有一个数出现次数为1次,其余数出现次数均为2次,我们只需要将他们全部异或起来就能得到结果,代码如下

class Solution 
{
public:int singleNumber(vector<int>& nums) {int res = 0;for (auto e : nums) res ^= e;return res;}
};

5. 只出现一次的数字Ⅲ

题目链接:260. 只出现一次的数字 III - 力扣(LeetCode)

解析:这道题中,有两个数字只出现一次(这里以3(011)和5(101)举例),那么将所有的数异或起来之后,会得到这两个数的异或结果(6(110)),由于异或的性质是相异为1,所以我们可以提取最右边的1(这个1代表3和5在这个位置不同),以它作为标志将整个数组分为2组,再次分别将所有数据异或便可以得到结果,代码如下

class Solution 
{
public:vector<int> singleNumber(vector<int>& nums) {int tmp = 0;for (int e : nums) tmp ^= e;// 取得最后一位1// 当tmp为INT_MIN时,即负数的最高位为 1,直接对其取反会导致溢出,需要特殊判断int flag = tmp == INT_MIN ? tmp : tmp & (-tmp);int e1 = 0, e2 = 0;for (int e : nums){if (flag & e) e1 ^= e;else e2 ^= e;}return { e1, e2 };}
};

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

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

相关文章

如何系统地学习Python

建议系统学习Python的途径遵循理论与实践相结合的教学方法。以下是一个分阶段的学习计划&#xff1a; 阶段一&#xff1a;基础知识 理解Python的特点&#xff1a; 认识Python的历史与设计哲学。学习Python的基本语法和运行环境。 安装Python&#xff1a; 学习如何在不同操作系…

(03)Hive的相关概念——分区表、分桶表

目录 一、Hive分区表 1.1 分区表的概念 1.2 分区表的创建 1.3 分区表数据加载及查询 1.3.1 静态分区 1.3.2 动态分区 1.4 分区表的本质及使用 1.5 分区表的注意事项 1.6 多重分区表 二、Hive分桶表 2.1 分桶表的概念 2.2 分桶表的创建 2.3 分桶表的数据加载 2.4 …

OpenAI最新模型Sora到底有多强?眼见为实的真实世界即将成为过去!

文章目录 1. 写在前面2. 什么是Sora&#xff1f;3. Sora的技术原理 【作者主页】&#xff1a;吴秋霖 【作者介绍】&#xff1a;Python领域优质创作者、阿里云博客专家、华为云享专家。长期致力于Python与爬虫领域研究与开发工作&#xff01; 【作者推荐】&#xff1a;对JS逆向感…

【MySQL】:C/C++链接

C/C链接 一.前置工作二.官方手册三.基本接口1.初始化和关闭2.进行连接3.下达命令4.获取执行结果5.释放空间 四.测试源代码 一.前置工作 进行C/C链接时我们需要第三方库&#xff0c;但实际上在我们安装MySQL时就已经安装了&#xff0c;如果没有安装下面可以再执行该命令进行更新…

【解决(几乎)任何机器学习问题】:超参数优化篇(超详细)

这篇文章相当长&#xff0c;您可以添加至收藏夹&#xff0c;以便在后续有空时候悠闲地阅读。 有了优秀的模型&#xff0c;就有了优化超参数以获得最佳得分模型的难题。那么&#xff0c;什么是超参数优化呢&#xff1f;假设您的机器学习项⽬有⼀个简单的流程。有⼀个数据集&…

【Kuiperinfer】笔记01 项目预览与环境配置

学习目标 实现一个深度学习推理框架设计、编写一个计算图实现常见的算子&#xff0c;例如卷积、池化、全连接学会如何进行算子的优化加速使用自己的推理框架推理常见模型&#xff0c;检查结果是否能够和torch对齐 什么是推理框架&#xff1f; 推理框架用于对已经训练完成的模…

基于Spring Boot的智能物流管理系统,计算机毕业设计(带源码+论文)

源码获取地址&#xff1a; 码呢-一个专注于技术分享的博客平台一个专注于技术分享的博客平台,大家以共同学习,乐于分享,拥抱开源的价值观进行学习交流http://www.xmbiao.cn/resource-details/1759581137025445890

npm ERR! network This is a problem related to network connectivity.

遇到 ETIMEDOUT 错误时&#xff0c;这表明npm尝试连接到npm仓库时超时了&#xff0c;这通常是由网络连接问题引起的。这可能是因为网络不稳定、连接速度慢、或者你的网络配置阻止了对npm仓库的访问。以下是一些解决这个问题的步骤&#xff1a; 1. 检查网络连接 首先&#xff…

java的泛型【详解】

定义类、接口、方法时&#xff0c;同时声明了一个或者多个类型变量&#xff08;如&#xff1a;<E>&#xff09; &#xff0c;称为泛型类、泛型接口&#xff0c;泛型方法、它们统称为泛型。 作用&#xff1a;泛型提供了在编译阶段约束所能操作的数据类型&#xff0c;并自…

Qt 使用QScintilla 编辑lua 脚本

需求&#xff1a; 利用QScintilla 编辑lua 脚本 步骤&#xff1a; 1&#xff0c;下载 QScintilla Riverbank Computing | Download 2, 打开 src/qscintilla.pro 文件 编译出 dll库 3&#xff0c;工程中引入这个库 注意debug 模式 必须加载debug 版本编译的库&#xff0…

Yii2项目使用composer异常记录

问题描述 在yii2项目中&#xff0c;使用require命令安装依赖时&#xff0c;出现如下错误提示 该提示意思是&#xff1a;composer运行时&#xff0c;执行了yiisoft/yii2-composer目录下的插件&#xff0c;但是该插件使用的API版本是1.0&#xff0c;但是当前的cmposer版本提供的…

Selenium实现多页面切换

当使用 Selenium 进行自动化测试或爬取数据时&#xff0c;有时需要处理多个页面之间的切换。以下是一些可能需要多页面切换的情况&#xff1a; 1、打开新窗口/页面&#xff1a; 在当前页面上点击链接、按钮或执行某些操作时&#xff0c;可能会打开一个新的窗口或页面。此时&a…

MySQL 基础知识(六)之数据查询(一)

目录 1 基本查询 1.1 查询相关列 (select * / 列名) 1.2 别名 (as) 1.3 去重 (distinct) 1.4 对列中的数据进行运算 (、-、*、/) 2 条件查询 (where) 2.1 等值查询 () 2.2 非等值查询 (>、<、>、<、!、><) 2.3 逻辑判断 (and、or、not) 2.4 区间判…

matlab发送串口数据,并进行串口数据头的添加,我们来看下pwm解析后并通过串口输出的效果

uintt16位的话会在上面前面加上00&#xff0c;16位的话一定是两个字节&#xff0c;一共16位的数据 如果是unint8的话就不会&#xff0c; 注意这里给的是13&#xff0c;但是现实的00 0D&#xff0c;这是大小端的问题&#xff0c;在matlanb里设置&#xff0c;我们就默认用这个模式…

更快找到远程/自由工作的网站

不要使用Fiver或Upwork。 它们已经饱和了。 下面是10个更快找到远程/自由工作的网站&#xff1a; 1. Toptal 这个网站专门为熟练的自由职业者提供远程工作机会&#xff0c;如Shopify和Priceline等一流公司。 他们只接受软件开发、设计和金融等领域的顶级3%自由职业者。 htt…

普中51单片机学习(九)

蜂鸣器 蜂鸣器简介 在单片机应用的设计上&#xff0c;很多方案都会用到蜂鸣器&#xff0c;大部分都是使用蜂鸣器来做提示或报警&#xff0c;比如按键按下、开始工作、工作结束或是故障等等。改变单片机引脚输出波形的频率&#xff0c;就可以调整控制蜂鸣器音调&#xff0c;产…

问题:从完整的问题解决过程来看,( )是首要环节。A.理解问题 B.提出假设C.发现问题 D.检验假设 #学习方法#学习方法

问题&#xff1a;从完整的问题解决过程来看&#xff0c;&#xff08; &#xff09;是首要环节。A&#xff0e;理解问题 B&#xff0e;提出假设C&#xff0e;发现问题 D&#xff0e;检验假设 A.理解问题 B.提出假设 C&#xff0e;发现问题 参考答案如图所示

Eclipse - Switch Workspace

Eclipse - Switch Workspace References Switch Workspace References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/

代码随想录算法训练营DAY20 | 二叉树 (8)

一、LeetCode 701 二叉搜索树中的插入操作 题目链接&#xff1a; 701.二叉搜索树中的插入操作https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/ 思路&#xff1a;见缝插针罢辽。 class Solution {public TreeNode insertIntoBST(TreeNode root, i…

vue3项目配置按需自动导入API组件unplugin-auto-import

场景应用&#xff1a;避免写一大堆的import&#xff0c;比如关于Vue和Vue Router的 1、安装unplugin-auto-import npm i -D unplugin-auto-import 2、配置vite.config import AutoImport from unplugin-auto-import/vite//按需自动加载API插件 AutoImport({ imports: ["…