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

【位运算】算法实战

文章目录

  • 一、算法原理
    • 常见的位运算总结
  • 二、算法实战
    • 1. leetcode面试题01.01. 判断字符是否唯一
    • 2. leetcode268 丢失的数字
    • 3. leetcode371 两整数之和
    • 4. leetcode004 只出现一次的数字II
    • 5. leetcode面试题17.19. 消失的两个数字
  • 三、总结


一、算法原理

计算机中的数据都以二进制形式存储和处理,位运算直接对二进制位进行操作。常见的位运算符包括与(&)、或(|)、异或(^)、取反(~)和左移(<<)、右移(>>)等。

在这里插入图片描述


常见的位运算总结

  1. 基础位运算
    在这里插入图片描述
  2. 给一个数n,确定它的二进制表示中第x位是0还是1
    在这里插入图片描述
  3. 将一个数n的二进制表示的第x位修改成1
    在这里插入图片描述
  4. 将一个数n的二进制表示的第x位修改成0
    在这里插入图片描述
  5. 位图的思想
    在这里插入图片描述
  6. 提取一个数(n)二进制表示中最右侧的1
    在这里插入图片描述
  7. 干掉一个数(n)二进制表示中最右侧的1
    在这里插入图片描述
  8. 位运算的优先级: 能加括号就加括号
  9. 异或(^)运算的运算律
    在这里插入图片描述

二、算法实战

1. leetcode面试题01.01. 判断字符是否唯一

在这里插入图片描述
判断字符是否唯一

解题思路:位图的思想

这道题目我们可以使用位图的思想来解决,因为题目告诉我们字符串中只有小写字母,所以我们只需要一个int类型的整数来充当位图的32个bit位即可。

首先,将位图的所有bit位置为零,默认字符串中的字符都未在位图中出现过。然后遍历整个字符串,检测该字符是否在位图中出现过,如果当前字符未在位图中出现过,说明当前字符是第一次出现,此时我们将其在位图中的位置(当前字符-'a')置为1即可,然后接着向后遍历字符串,如果该字符再次出现,我们就可以从位图中检测到该字符已经在出现过了。直接返回false即可,否则继续向后遍历字符串,如果遍历所有字符后发现都只出现一次,则说明该字符串符合题意。

代码实现:

class Solution {
public:bool isUnique(string astr) {int num = 0;for(int i = 0; i < astr.size(); i++){int index = astr[i] - 'a';if(((num>>index) & 1) == 1)return false;elsenum |= 1 << index;}return true;}
};

2. leetcode268 丢失的数字

在这里插入图片描述
丢失的数字

解题思路:异或运算

因为题目中告诉我们数组中【1~n】丢失了一个数字,所以我们可以先将数组中的数字 ^ 起来,然后在将这个 ^ 的结果与【1~n】中所有的数字异或,因为按位 ^ 运算满足交换律和结合律,所以按位 ^ 的结果中,丢失的数字出现了一次,其余的数字都出现了两次,将这一堆数字异或起来,结果即为丢失的数字。

在这里插入图片描述

代码实现:

class Solution {
public:int missingNumber(vector<int>& nums) {int ret = 0;for(auto e : nums)ret ^= e;for(int i = 1; i <= nums.size(); i++)ret ^= i;return ret;}
};

3. leetcode371 两整数之和

在这里插入图片描述
两整数之和

解题思路:异或运算-无进位相加

因为题目要求我们不能使用运算符+-来计算两整数之和,因此我们可以将整数 a 和 b 的和,拆分为 a 和 b 的无进位相加结果进位结果的和无进位相加结果 我们可以使用两整数^来实现,进位结果我们可以使用(a & b) << 1来实现。下面我们来举一个例子:

在这里插入图片描述

每次将无进位相加结果进位结果的和分别赋予a和b,循环此过程,直到进位为 0。最终a就是我们所要求的结果。当我们赋给无符号类型一个超出它表示范围的值时,结果是初始值对无符号类型表示数值总数取模的余数。因此,我们可以使用无符号类型来防止溢出。

代码实现:

lass Solution {
public:int getSum(int a, int b) {while(b != 0){int x = a ^ b; // 先算出无进位相加的结果unsigned int carry = (a & b) << 1; // 算出进位a = x;b = carry;}return a;}
};

4. leetcode004 只出现一次的数字II


只出现一次的数字II

解题思路:

数组中的每个元素的每一个二进制位不是1就是0,而题目中又告诉我们只有一个元素出现一次,其余元素都出现了三次,所以对于数组中的每一个元素 x,我们使用位运算 (x >> i) & 1 得到 x 的第 i 个二进制位,并将它们相加再对 3 取余,得到的结果一定为 0 或 1,即为答案的第 i 个二进制位。

所以,答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。可以先初始化一个ret = 0,然后根据余数的值来判断该数对应的二进制位应该置为0还是1,如果余数为1,我们则需要手动将该位置置为1,ret |= (1 << i),否则则不需要处理。

代码实现:

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int cnt = 0;for(auto e : nums)cnt += ((e>>i)&1);if(cnt % 3)ret |= (1 << i);}return ret;}
};

5. leetcode面试题17.19. 消失的两个数字

在这里插入图片描述
消失的两个数字

解题思路:

这道题目其实我们可以用力扣的第260题 只出现一次的数字III 的思想来做,具体解决方式如下:

因为数组中包含从 1 到 N 所有的整数,但其中缺了两个数字,现在数组的长度为n。所以数组中原本应该包含的数字是【1,n + 2】。我们可以将原来数组中的数字和【1,n + 2】,组合到一起,现在我们就可以将问题转化一下:求数组中只出现一次的两个数字。

解决这个问题我们可以分为两步:整体异或分组异或。整体异或:将题目给出的数组中的所有数字和【1,n + 2】中所包含的数字全部异或起来,得到的结果就是只出现一次的两个数字的异或结果:a^b。接下来我们需要提取出该数字二进制表示中最低位的1。假设该位置为第k位,我们就可以把 所有数中的元素(题目中给出的数字和【1,n + 2】的数字)分成两类,其中一类包含所有二进制表示的第 k 位为 0 的数,另一类包含所有二进制表示的第 k 位为 1 的数。

  • 对于任意一个在 所有元素中 出现两次的元素,该元素的两次出现会被包含在同一类中;
  • 对于任意一个在所有元素中只出现了一次的元素,即 x1 和 x2, 他们会被包含在不同的类中。

因此,我们将这两类元素分别异或起来,就可以得到不同的两个结果,一个结果是x1,另一个结果是x2,这两个数字则是只出现一次的两个数字,即本题中我们需要寻找的两个消失的数字。

代码实现:

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int ret = 0;for(int i = 1; i <= nums.size()+2; i++)ret ^= i;for(auto e : nums) ret ^= e;int lowbit = ret & -ret; // 找出最后一个不同的比特位int ret1 = 0, ret2 = 0;for(int i = 1; i <= nums.size()+2; i++){ // 分组异或if(lowbit & i) ret1 ^= i;else ret2 ^= i;}for(auto e : nums){if(lowbit & e) ret1 ^= e;else ret2 ^= e;}return {ret1, ret2};}
};

三、总结

位运算可以直接操控数字的二进制位,节约内存,使程序运行更快,可靠性高。在算法中使用位运算可以大大降低算法的时间复杂度和空间复杂度,恰当的位运算使用也能使程序变得更加简洁和优美。

相关文章:

【位运算】算法实战

文章目录 一、算法原理常见的位运算总结 二、算法实战1. leetcode面试题01.01. 判断字符是否唯一2. leetcode268 丢失的数字3. leetcode371 两整数之和4. leetcode004 只出现一次的数字II5. leetcode面试题17.19. 消失的两个数字 三、总结 一、算法原理 计算机中的数据都以二进…...

C++构建系统

收集C构建系统(2023)&#xff1a; 跟我一起写Makefile (PDF重制版)CMake tutorialConan, software package manager for C and C developersvcpkg-repovcpkgGoogle Bazel Build System { Fast, Correct } — Choose twoGN gn_quick_start当前Chromium构建系统 GYP Generate You…...

“深入探索JVM内部机制:理解Java虚拟机的运行原理“

标题&#xff1a;深入探索JVM内部机制&#xff1a;理解Java虚拟机的运行原理 摘要&#xff1a;本篇博客将深入探索Java虚拟机&#xff08;JVM&#xff09;的内部机制&#xff0c;帮助读者理解JVM的运行原理。我们将介绍JVM的组成结构&#xff0c;包括类加载器、运行时数据区域…...

java八股文面试[JVM]——双亲委派模型

1.当AppClassLoader去加载一个class时&#xff0c;它首先不会自己去尝试加载这个类&#xff0c;而是把类加载请求委托给父加载器ExtClassLoader去完成。 2.当ExtClassLoader去加载一个class时&#xff0c;它首先也不会去尝试加载这个类&#xff0c;而是把类加载请求委托给父加载…...

NLP与大模型主题全国师资培训班落地,飞桨持续赋能AI人才培养

为了推动大模型及人工智能相关专业人员的培养&#xff0c;8月11日-8月13日&#xff0c;由中国计算机学会主办、机械工业出版社、北京航空航天大学、百度飞桨联合承办 “CCF群星计划之文心高校行- NLP与大模型”主题师资培训班&#xff08;以下简称培训班&#xff09;在北京天信…...

Jupyter Notebook 配置根目录

注&#xff1a;本文是在 Windows 10 上配置 Jupyter Notebook 打开的默认根目录&#xff0c;Linux 同。 步骤一&#xff1a;创建 Jupyter Notebook 配置文件 使用以下命令创建 Jupyter Notebook 配置文件&#xff08;如果尚未创建&#xff09;&#xff1a; jupyter notebook …...

算法 位运算

文章目录 一、&&#xff08;按位与&#xff09;运算符二、|&#xff08;按位或&#xff09;运算符三、^&#xff08;异或&#xff09;运算符四、~&#xff08;取反&#xff09;运算符五、<<&#xff08;左移&#xff09;运算符六、>>&#xff08;右移&#xff…...

Linux 虚拟机常用命令

一、文件/文件夹管理 1. ls命令 就是 list 的缩写&#xff0c;通过 ls 命令不仅可以查看 linux 文件夹包含的文件&#xff0c;而且可以查看文件权限(包括目录、文件夹、文件权限)查看目录信息等等。 ls -a 列出目录所有文件&#xff0c;包含以.开始的隐藏文件ls -A 列出除.…...

解决抖音semi-ui的Input无法获取到onChange事件

最近在使用semi-ui框架的Input实现一个上传文件功能时遇到了坑&#xff0c;就是无法获取到onChange事件&#xff0c;通过console查看只是拿到了一个文件名。但若是把<Input>换成原生的<input>&#xff0c;就可以正常获取到事件。仔细看了下官方文档&#xff0c;发现…...

免费的png打包plist工具CppTextu,一款把若干资源图片拼接为一张大图的免费工具

经常做游戏打包贴图的都知道&#xff0c;要把图片打包为一张或多张大图&#xff0c;要使用打包工具TexturePacker。 TexturePacker官方版可以直接导入PSD、SWF、PNG、BMP等常见的图片格式&#xff0c;主要用于网页、游戏和动画的制作&#xff0c;它可以将多个小图片汇聚成一个…...

深层次分析字符数组和字符串的区别是什么?

前言 &#xff08;1&#xff09;休闲时刻刷B站&#xff0c;看到一个卖课的&#xff0c;发视频问&#xff0c;char arr1[]{‘H’,‘E’,‘L’,‘L’,‘O’};和char arr2[]“HELLO”;区别是什么。 &#xff08;2&#xff09;看那个卖课博主一顿分析&#xff0c;最后成功得出&…...

Redis 的主从复制、哨兵模式、集群脑裂

主从复制 主从复制是 Redis 高可用服务最基础的保证&#xff0c;将一台 Redis 主服务器&#xff0c;同步数据到多台 Redis 从服务器上&#xff0c;即一主多从的模式&#xff0c;且主从服务器之间采用的是「读写分离」的方式。 主服务器可以进行读写操作&#xff0c;当发生写操…...

Pycharm通过SSH配置centos上Spark环境

直接在shell进行pyspark进行编程&#xff0c;程序没有办法写得太长&#xff0c;而且我们希望能够实现一个及时给出结果的编程环境&#xff0c;可以使用pycharm连接centos上的spark&#xff0c;进行本地编程&#xff0c;同步到centos系统中运行程序&#xff0c;并把结果返回pych…...

leetcode做题笔记98. 验证二叉搜索树

给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 思路一&#xff1a;递归 …...

C# 中Lambda中的的匿名函数

/// <summary>/// 根据设备号&#xff0c;获取故障列表/// </summary>/// <param name"scanCode">主键</param>/// <returns></returns>[HttpGet]public async Task<IActionResult> GetItemPageList(string scanCode){//v…...

铰接式车辆的横向动力学仿真提供车辆模型研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Ubuntu20 安装 libreoffice

1 更新apt-get sudo apt-get update2 安装jdk 查看jdk安装情况 Command java not found, but can be installed with:sudo apt install default-jre # version 2:1.11-72, or sudo apt install openjdk-11-jre-headless # version 11.0.138-0ubuntu1~20.04 sud…...

HTTP协议(JavaEE初阶系列15)

目录 前言&#xff1a; 1.HTTP协议 1.1HTTP协议是什么 1.2HTTP协议的报文格式 1.2.1抓包工具的使用 1.2.2HTTP请求 1.2.3HTTP响应 2.HTTP请求 2.1首行的组成 2.2.1URL的组成 2.2认识“方法”&#xff08;method&#xff09; 2.2.1GET方法 2.2.2POST方法 2.2.3GET…...

机器学习基础10-审查回归算法(基于波士顿房价的数据集)

上一节介绍了如何审查分类算法&#xff0c;并介绍了六种不同的分类算法&#xff0c;还 用同一个数据集按照相同的方式对它们做了审查&#xff0c;本章将用相同的方式对回归算法进行审查。 在本节将学到&#xff1a; 如何审查机器学习的回归算法。如何审查四种线性分类算法。如…...

基于 CentOS 7 构建 LVS-DR 群集。配置nginx负载均衡。

1、基于 CentOS 7 构建 LVS-DR 群集。 [root132 ~]# nmcli c show NAME UUID TYPE DEVICE ens33 c89f4a1a-d61b-4f24-a260-6232c8be18dc ethernet ens33 [root132 ~]# nmcli c m ens33 ipv4.addresses 192.168.231.200/24 [r…...

癫痫手术精准定位:基于脑电信号昼夜节律与多生物标志物的机器学习分析框架

1. 项目概述&#xff1a;当机器学习遇见脑电信号&#xff0c;如何让癫痫手术更精准&#xff1f;作为一名长期耕耘在生物医学信号处理与机器学习交叉领域的工程师&#xff0c;我常常思考如何将算法模型从实验室的“玩具”变成临床医生手中可靠的“手术刀”。癫痫&#xff0c;这个…...

CPU架构启发的智能仓储布局优化实践

1. 仓库布局优化的核心挑战与创新机遇在物流仓储领域&#xff0c;拣货环节通常占据运营成本的55%-65%&#xff0c;而其中约50%的时间消耗在无效行走路径上。传统矩形仓库布局虽然易于规划和施工&#xff0c;但其正交的通道设计导致拣货员需要频繁进行90度转向&#xff0c;这种&…...

从模糊到电影级景深:Midjourney + Topaz Gigapixel联调方案(含LUT预设包+PSD分层模板)

更多请点击&#xff1a; https://codechina.net 第一章&#xff1a;从模糊到电影级景深&#xff1a;Midjourney Topaz Gigapixel联调方案&#xff08;含LUT预设包PSD分层模板&#xff09; 当Midjourney生成的图像存在主体边缘柔化、背景层次缺失或分辨率不足等问题时&#xf…...

3步快速部署:智能茅台抢购平台的终极自动化解决方案

3步快速部署&#xff1a;智能茅台抢购平台的终极自动化解决方案 【免费下载链接】campus-imaotai i茅台app自动预约&#xff0c;每日自动预约&#xff0c;支持docker一键部署&#xff08;本项目不提供成品&#xff0c;使用的是已淘汰的算法&#xff09; 项目地址: https://gi…...

PostgreSQL Join 执行策略(Nested Loop、Hash Join、Merge Join)与 NOT EXISTS 优化

以集成数据压缩 SQL 优化为例&#xff0c;用大白话讲清楚 Nested Loop、Hash Join、Merge Join 三种执行策略。一、背景&#xff1a;一条慢 SQL 引发的思考 在对上游下发数据做压缩时&#xff0c;有这样一条 UPDATE SQL&#xff1a; -- ❌ 原始写法 UPDATE magellan_nk_order_i…...

计算机视觉的实战项目:从0到1搭建属于自己的图像识别系统

作为软件测试从业者&#xff0c;我们每天都在和各类功能验证、兼容性测试、自动化测试框架打交道&#xff0c;对AI领域的实战项目往往觉得“门槛高”“和日常工作不沾边”。但随着AI技术在互联网产品中的落地越来越深入&#xff0c;图像识别功能已经成为很多APP、智能硬件的核心…...

SMUDebugTool:AMD Ryzen处理器深度调试与性能调优完全指南

SMUDebugTool&#xff1a;AMD Ryzen处理器深度调试与性能调优完全指南 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: https:…...

DeepSeek模型选型终极指南(附完整Benchmark Excel模板):从MMLU到GPQA、从AIME到LiveCodeBench,一表看透真实能力边界

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;DeepSeek模型选型终极指南&#xff08;附完整Benchmark Excel模板&#xff09;&#xff1a;从MMLU到GPQA、从AIME到LiveCodeBench&#xff0c;一表看透真实能力边界 选择适配业务场景的DeepSeek模型&am…...

从无人机到自动驾驶:一文读懂ROS中ENU、NED、相机坐标系到底怎么用

从无人机到自动驾驶&#xff1a;ROS中ENU、NED与相机坐标系实战指南 当你在无人机上安装Realsense相机时&#xff0c;是否遇到过相机数据与飞控数据"对不上"的情况&#xff1f;或者在自动驾驶项目中&#xff0c;GPS的北东地坐标如何与激光雷达的东北天坐标对齐&#…...

Unity Cinemachine相机系统深度使用:除了自动跟随,它的边界限制(Confiner)功能才是宝藏

Unity Cinemachine Confiner&#xff1a;解锁专业级镜头边界控制的实战指南在游戏开发中&#xff0c;镜头控制往往是被低估的艺术。许多开发者对Cinemachine的印象停留在"智能跟随相机"层面&#xff0c;却不知道它的Confiner功能能够彻底改变游戏镜头的专业度。想象一…...