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

算法->位运算

有关位运算的操作符

  • >>
  • <<
  • &
  • |
  • ^
  • ~

常见位运算操作

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

(n >> x) & 1;

将一个数n的二进制中第x位修改为1

n |= (1 << x)

将一个数n的二进制中第x位修改为0

n &= (~(1 << x))

提取一个数二进制中最右侧的1

n & (-n)

去掉一个数中二进制最右侧的1

n & (n-1)

异或运算律

  • a ^ a = 0
  • a ^ 0 = a
  • a ^ b ^ c = a ^ (b ^ c)

191. 位1的个数 - 力扣(LeetCode)

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
示例 1:

输入: n = 00000000000000000000000000001011
输出: 3
解释: 输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入: n = 00000000000000000000000010000000
输出: 1
解释: 输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入: n = 11111111111111111111111111111101
输出: 31
解释: 输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

解题思路

n & (n-1)每次可以干掉二进制中最右侧的1

代码实现

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

338. 比特位计数 - 力扣(LeetCode)

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1:

输入: n = 2
输出: [0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10

示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

解题思路

利用n&(n-1)从最高位开始统计位1的个数,将结果存放到vector中即可。时间复杂度O(n^2)

代码实现

class Solution 
{
public:vector<int> countBits(int n) {vector<int> ans(n+1);while(n >= 0){int ret = 0,tmp = n;while(tmp != 0){tmp = tmp & (tmp-1);ret++;}ans[n--] = ret;}return ans;}
};

461. 汉明距离 - 力扣(LeetCode)

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

示例 1:

输入: x = 1, y = 4
输出: 2
解释:
1   (0 0 0 1)
4   (0 1 0 0)

解题思路

异或后求二进制位1的个数即可

代码实现

class Solution 
{
public:int hammingDistance(int x, int y) {//异或,求异或后二进制1的个数即可int ret = x ^ y;int sum = 0;while(ret != 0){   ret &= (ret-1);sum++;}return sum;}
};

136. 只出现一次的数字 - 力扣(LeetCode)

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1 :

输入: nums = [2,2,1]
输出: 1

示例 2 :

输入: nums = [4,1,2,1,2]
输出: 4

示例 3 :

输入: nums = [1]
输出: 1

解题思路

  • a^0 = a;
  • a^a = 0;
  • abc = a(bc)
  • 41212 = 4(11)(22)
  • 空间复杂度要求O(n) 不能使用哈希表

代码实现

class Solution 
{
public:int singleNumber(vector<int>& nums) {//a^0 = a;//a^a = 0;//a^b^c = a^(b^c)//4^1^2^1^2 = 4^(1^1)^(2^2)int ret = 0;for(auto &e : nums){ret ^= e;}return ret;}
};

面试题 01.01. 判定字符是否唯一 - 力扣(LeetCode)

实现一个算法,确定一个字符串 s 的所有字符是否全都不同。

示例 1:

输入: s = "leetcode"
输出: false 

示例 2:

输入: s = "abc"
输出: true

限制:

  • 0 <= len(s) <= 100
  • s[i]仅包含小写字母
  • 如果你不使用额外的数据结构,会很加分。

解题思路

  • 哈希表。
    • 字符串中仅包含小写字母,使用数组模拟哈希表即可。时间复杂度O(n);
  • 位运算
    • 位图思想 26个比特位即可(一个字节即可)

代码实现

class Solution 
{
public:bool isUnique(string astr) {if(astr.size() > 26){return false;}//哈希表// int hash[26] = {0};// for(size_t i = 0; i < astr.size(); ++i)// {//     hash[astr[i] - 'a']++;// }// for(auto e : hash)// {//     if(e >= 2 ) return false;// }// return true;// 位图int bit_map = 0;for(auto e : astr){int index = e - 'a';//判断是否在位图中。if((bit_map >> index) & 1 == 1) return false;//加入位图bit_map |= (1 << index);}return true;}
};

268. 丢失的数字 - 力扣(LeetCode)

给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1:

输入: nums = [3,0,1]
输出: 2
解释: n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 2:

输入: nums = [0,1]
输出: 2
解释: n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 3:

输入: nums = [9,6,4,2,3,5,7,0,1]
输出: 8
解释: n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

示例 4:

输入: nums = [0]
输出: 1
解释: n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

解题思路

  • 哈希表
  • 高斯求和
  • 异或运算符
class Solution 
{
public:int missingNumber(vector<int>& nums) {//哈希表// int hash[10000] = {0};// //存放到哈希表中// for(size_t i = 0; i < nums.size();++i)// {//     hash[nums[i]]++;// }// //遍历哈希表// for(size_t i =0 ; i < 10000; i++)// {//     if(hash[i] ==0 ) return i;// }// return 0;//高斯求和// size_t n = nums.size();// int sum = 0;// for(size_t i = 0; i < n ; ++i)// {//     sum += nums[i];// }// return ((n) * (n +1) / 2 ) - sum;//位运算(异或运算律)int ret = 0;for(auto e : nums){ret ^= e;}for(int i = 0; i < nums.size() + 1 ; ++i){ret ^= i;}return ret;}};

相关文章:

算法->位运算

有关位运算的操作符 >> <<&|^~ 常见位运算操作 给定一个数&#xff0c;确定它的二进制中第x位是0还是1 (n >> x) & 1; 将一个数n的二进制中第x位修改为1 n | (1 << x) 将一个数n的二进制中第x位修改为0 n & (~(1 << x)) 提…...

【Python】成功解决ModuleNotFoundError: No module named ‘matplotlib‘

【Python】成功解决ModuleNotFoundError: No module named ‘matplotlib’ &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448…...

centos7中python3.10找不到openssl解决方案

如果有用其他方法安装了其他版本openssl&#xff0c;记得卸载其他的openssl&#xff0c;删除其他的openssl相关文件。 yum remove openssl* rm -rf ***下载最新版的openssl文件 按照官网安装方法安装openssl 官方安装地址https://docs.python.org/3/using/unix.html#on-linu…...

【Spring Boot `@Autowired` Annotation】

文章目录 1. 使用Qualifier注解2. 使用Primary注解3. 手动注入&#xff08;较少推荐&#xff09; 在Spring Boot中&#xff0c;Autowired注解用于自动装配bean。默认情况下&#xff0c;它按照类型进行装配。当存在多个相同类型的bean时&#xff0c;就会出现以下错误&#xff1a…...

03.axios数据提交和错误处理

一.axios常用请求方法和数据提交 1. 想要提交数据&#xff0c;先来了解什么是请求方法 请求方法是一些固定单词的英文&#xff0c;例如&#xff1a;GET&#xff0c;POST&#xff0c;PUT&#xff0c;DELETE&#xff0c;PATCH&#xff08;这些都是http协议规定的&#xff09;&am…...

无人机生态环境监测、图像处理与GIS数据分析

构建“天空地”一体化监测体系是新形势下生态、环境、水文、农业、林业、气象等资源环境领域的重大需求&#xff0c;无人机生态环境监测在一体化监测体系中扮演着极其重要的角色。通过无人机航空遥感技术可以实现对地表空间要素的立体观测&#xff0c;获取丰富多样的地理空间数…...

centos7.9升级ssh和openssl

一、环境 [roottmp179 package]# ssh -V OpenSSH_7.4p1, OpenSSL 1.0.2k-fips 26 Jan 2017 [roottmp179 package]# cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core) 二、 升级前准备 mkdir /opt/package cd /opt/package wget https://www.openssl.org/source…...

HttpURLConnection详解及使用

HttpURLConnection 请求响应流程 设置连接参数的方法 setAllowUserInteractionsetDoInputsetDoOutputsetIfModifiedSincesetUseCachessetDefaultAllowUserInteractionsetDefaultUseCaches 发送URL请求 建立实际连接之后&#xff0c;就是发送请求&#xff0c;把请求参数传到…...

npm下载时下载失败解决方法

1.清楚缓存 npm cache clean --force2.切换下载镜像 1.查看当前使用的镜像地址命令 npm config get registry切换为淘宝镜像命令&#xff08;安装一些package容易报错&#xff09; npm config set registry https://registry.npm.taobao.org或官方&#xff1a; npm config…...

Python实战:浅析Python输入输出理解数据交换的基本原理

在Python编程中&#xff0c;输入输出是数据交换的基础。本文将深入探讨Python中的输入输出功能&#xff0c;包括标准输入输出、文件输入输出、格式化输出等。我们将通过具体的代码示例来展示如何使用Python进行数据输入和输出&#xff0c;并理解其背后的工作原理。 1. 标准输入…...

MySQL--explain执行计划详解

什么是执行计划&#xff1f; SQL的执行计划&#xff0c;通俗来说就是SQL的执行情况&#xff0c;一条SQL语句扫描哪些表&#xff0c;那个子查询先执行&#xff0c;是否用到了索引等等&#xff0c;只有当我们知道了这些情况之后才知道&#xff0c;才可以更好的去优化SQL&#xf…...

【NERF】入门学习整理(一)

【NERF】入门学习整理 1. 【NERF】入门学习整理1.1 基础含义输入输出2.位置编码含义3.代码中实际网路结构4.Volume Render部分(64个采样点处理)5.Volume Render部分(64个采样点处理)【NERF】及其变种(二) 1. 【NERF】入门学习整理 1.1 基础含义输入输出 深度学习模型中…...

基于ZYNQ PS-SPI的Flash驱动开发

本文使用PS-SPI实现Flash读写&#xff0c;PS-SPI的基础资料参考Xilinx UG1085的文档说明&#xff0c;其基础使用方法是&#xff0c;配置SPI模式&#xff0c;控制TXFIFO/RXFIFO&#xff0c;ZYNQ的IP自动完成发送TXFIFO数据&#xff0c;接收数据到RXFIFO&#xff0c;FIFO深度为12…...

Linux Shell:local关键字

Linux Shell&#xff1a;local关键字 在 Bash 中&#xff0c;local 是一个用于声明局部变量的关键字。当在函数内部使用 local 声明变量时&#xff0c;该变量只能在函数内部使用&#xff0c;并且不会对函数外部的同名变量产生影响。这样可以确保在函数内部定义的变量不会意外地…...

如何开发python毕业设计

开发Python毕业设计需要以下步骤&#xff1a; 选择项目主题&#xff1a; 选择一个与你的兴趣和专业相关的主题。确保主题具有一定的挑战性&#xff0c;但又不至于过于复杂&#xff0c;以确保你能够在规定时间内完成项目。 制定项目计划&#xff1a; 制定一个清晰的项目计划&…...

D*算法超详解 (D星算法 / Dynamic A*算法/ Dstar算法)(死循环解决--跟其他资料不一样奥)

所需先验知识&#xff08;没有先验知识可能会有大碍&#xff0c;了解的话会对D*的理解有帮助&#xff09;&#xff1a;A*算法/ Dijkstra算法 何为D*算法 Dijkstra算法是无启发的寻找图中两节点的最短连接路径的算法&#xff0c;A*算法则是在Dijkstra算法的基础上加入了启发函数…...

django学习记录07——订单案例(复选框+ajax请求)

1.订单的数据表 1.1 数据表结构 1.2 数据表的创建 models.py class Order(models.Model):"""订单号"""oid models.CharField(max_length64, verbose_name"订单号")title models.CharField(max_length64, verbose_name"名称&…...

Qt 定时器事件

文章目录 1 定时器事件1.1 界面布局1.2 关联信号槽1.3 重写timerEvent1.4 实现槽函数 启动定时器 2 定时器类 项目完整的源代码 QT中使用定时器&#xff0c;有两种方式&#xff1a; 定时器类&#xff1a;QTimer定时器事件&#xff1a;QEvent::Timer&#xff0c;对应的子类是QTi…...

LLM 推理优化探微 (2) :Transformer 模型 KV 缓存技术详解

编者按&#xff1a;随着 LLM 赋能越来越多需要实时决策和响应的应用场景&#xff0c;以及用户体验不佳、成本过高、资源受限等问题的出现&#xff0c;大模型高效推理已成为一个重要的研究课题。为此&#xff0c;Baihai IDP 推出 Pierre Lienhart 的系列文章&#xff0c;从多个维…...

JavaEE进阶(15)Spring原理:Bean的作用域、Bean的生命周期、Spring Boot自动配置(加载Bean、SpringBoot原理分析)

接上次博客&#xff1a;JavaEE进阶&#xff08;14&#xff09;Linux基本使用和程序部署&#xff08;博客系统部署&#xff09;-CSDN博客 目录 关于Bean的作用域 概念 Bean的作用域 Bean的生命周期 源码阅读 Spring Boot自动配置 Spring 加载Bean 问题描述 原因分析 …...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...