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

算法思想总结:位运算

                                               创作不易,感谢三连支持!!

一、常见的位运算总结

标题

 

 

二、位1的个数

. - 力扣(LeetCode)

 利用第七条特性:n&(n-1)干掉最后一个1,然后每次都用count++去统计,直到变成0

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

 三、汉明距离

. - 力扣(LeetCode)

      利用异或相同为0相异为1的特点,x和y异或后不一样的位都会变成1,这个时候再用n&(n-1)去统计1个个数,即为这两个数字的汉明距离

class Solution {
public:int hammingDistance(int x, int y) {//异或的特点,相同为0,相异为1     然后再利用n&(n-1)统计1的个数int n=x^y;int count=0;while(n){n&=(n-1);++count;}return count;}
};

 四、比特数记位(典型dp)

思路1:每遍历一个数都用n&(n-1)去数他一共有多少个1,然后放心ans数组中

class Solution {
public:int countOnes(int x){int ones=0;while(x){x&=(x-1);++ones;}return ones;}//利用vector<int> countBits(int n) {vector<int> ret(n+1);for(int i=1;i<=n;++i)  ret[i]=countOnes(i);return ret;}
};

 思路2:动态规划思想(本质是根据位运算的性质通过已经计算出来的状态去求未计算的状态)

         即当计算 i 的「一比特数」时,如果存在 0≤j<i,j 的「一比特数」已知,且 i和 j 相比,i 的二进制表示只比j多了一个 1,则可以快速得到 i 的「一比特数」。(利用位运算的性质)

1、设置最低位

        对于n(n-1),本质上是将最右侧的1干掉,所以一定会比原来的n小!!

因此bit[i]=bit[i&(i-1)]+1  恒成立!!

class Solution {
public:vector<int> countBits(int n) {vector<int> ret(n+1);for(int i=1;i<=n;++i)  ret[i]=ret[i&(i-1)]+1;return ret;}
};

 2、最低有效位

      对于正整数x来说,如果是偶数的话,右移一位正好就是x/2,并且1的个数不会变,所以偶数bit[i]=bit[i/2]   对于奇数来说,右移一位会丢掉后面的1,所以要给他补上去,所以奇数等于bit[i]=bit[i/2]+1       为了修正奇数多出来的1,我们可以利用i&1,如果是奇数就是1,偶数就是0,因此   bit[i]=bit[i/2]+(i&1) 恒成立!!

class Solution {
public:vector<int> countBits(int n) {vector<int> ret(n+1);for(int i=1;i<=n;++i)  ret[i]=ret[i/2]+(i&1);return ret;}
};

3、最高有效位

       对于正整数 x,如果可以知道最大的正整数 y,使得 y≤x,y 是 2的整数次幂,则 y的二进制表示中只有最高位是 1,其余都是 0,此时称 y 为 x 的「最高有效位」。令 z=x−y,显然 0≤z<x,则 bits[x]=bits[z]+1,所以我们使用heightbit作为当前的最高有效位。如果i&(i-1)为最高有效位,就更新heightbit,i 比 i−highBit的「一比特数」多 1    所以bit[i]=bit[i-height]+1 恒成立!!

class Solution {
public:vector<int> countBits(int n) {vector<int> ret(n+1);int heightbit=0;for(int i=1;i<=n;++i)  {if((i&(i-1))==0)  heightbit=i;ret[i]=ret[i-heightbit]+1;}return ret;}
};

五、只出现一次的数字(1)

. - 力扣(LeetCode)

思路:利用异或的性质,出现两次的数异或后为0,出现一次的数异或0还是本身 

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

六、只出现一次的数字(2) 

. - 力扣(LeetCode)

class Solution {
public:int singleNumber(vector<int>& nums) {int ret=0;for(int i=0;i<32;++i){int sum=0;for(int num:nums)  if((num>>i)&1) ++sum;//统计个数每一个1的比特位sum%=3;//模3后代表ret当前bit位的值if(sum==1) ret|=(1<<i);//sum==1就让ret该位置变成1}return ret;}
};

七、只出现一次的数字(3)

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {unsigned int temp=0;//遇到INT_MIN会溢出,10000……00for(int num:nums) temp^=num;int x=temp&(-temp);//x拿到最后一个1//int x= (temp == temp ? temp : temp & (-temp));int type1=0,type2=0;for(int num:nums) if(num&x) type1^=num; else type2^=num;return {type1,type2};}
};

八、丢失的数字

. - 力扣(LeetCode)

思路1:利用等差数列和的公式-数组每一位数相加,即可得到消失的数

class Solution {
public:int missingNumber(vector<int>& nums) {int n=nums.size();return n*(n+1)/2-accumulate(nums.begin(),nums.end(),0);}
};

 思路2:利用异或的特点,让0和数组所有数进行异或,再对1-n异或,出现两次的数都会被消去,最后只会留下答案

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

思路3:暴力快排+寻找下标和数字对应不上的数 

class Solution {
public:int missingNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int n=nums.size();for(int i=0;i<n;++i) if(nums[i]!=i) return i;return n;}
};

九、消失的两个数字

. - 力扣(LeetCode)

该题就是只出现一次数组(1)和 (3)的结合,所以以上的思路去解答即可

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int temp=0;for(auto e:nums) temp^=e;for(int i=1;i<=nums.size()+2;++i) temp^=i;int x=temp&(-temp);//拿到最右边的1int num1=0,num2=0;for(auto e:nums) if(e&x) num1^=e;  else  num2^=e;for(int i=1;i<=nums.size()+2;++i) if(i&x) num1^=i;  else  num2^=i;return {num1,num2};}
};

十、判定字符是否唯一

. - 力扣(LeetCode)

 

class Solution {
public:bool isUnique(string astr) {if(astr.size()>26)  return false;//鸽巢原理做优化//利用位图的思想int bitmap=0;for(auto ch:astr){int i=ch-'a';//找到映射关系if((bitmap>>i)&1==1)  return false;//先判断该字符是否出现过 判断第i位是否是1//如果没出现过,将第i位的0修改为1bitmap|=(1<<i);}return true;}
};

十一、或运算的最小翻转次数

. - 力扣(LeetCode)

class Solution {
public:int minFlips(int a, int b, int c) {int ret=0;//记录翻转次数for(int i=0;i<31;++i){//找到每一位进行判断int bit_a=(a>>i)&1;int bit_b=(b>>i)&1;int bit_c=(c>>i)&1;//情况1,如果c为0的话,那么a和b必须全是0 所以他们是多少就要翻转几次if(bit_c==0) ret+=(bit_a+bit_b);//情况2,如果c为1的话,那么a和b至少要有一个为1    如果都为0,翻转一次,如果有1就不用翻转else ret+=(bit_a+bit_b==0);}return ret;}
};

十二、两整数之和

. - 力扣(LeetCode)

class Solution {
public:int getSum(int a, int b) {//要考虑-1,因为-1的右移操作是没有定义的while(b){int  x=a^b;int carry=(a&b)<<1;a=x;b=carry;}return a;}
};

相关文章:

算法思想总结:位运算

创作不易&#xff0c;感谢三连支持&#xff01;&#xff01; 一、常见的位运算总结 标题 二、位1的个数 . - 力扣&#xff08;LeetCode&#xff09; 利用第七条特性&#xff1a;n&&#xff08;n-1&#xff09;干掉最后一个1&#xff0c;然后每次都用count去统计&#xff…...

四、HarmonyOS应用开发-ArkTS开发语言介绍

目录 1、TypeScript快速入门 1.1、编程语言介绍 1.2、基础类型 1.3、条件语句 1.4、函数 1.5、类 1.6、模块 1.7、迭代器 2、ArkTs 基础&#xff08;浅析ArkTS的起源和演进&#xff09; 2.1、引言 2.2、JS 2.3、TS 2.4、ArkTS 2.5、下一步演进 3、ArkTs 开发实践…...

3 Spring之DI详解

5&#xff0c;DI相关内容 前面我们已经完成了bean相关操作的讲解&#xff0c;接下来就进入第二个大的模块DI依赖注入&#xff0c;首先来介绍下Spring中有哪些注入方式? 我们先来思考 向一个类中传递数据的方式有几种? 普通方法(set方法)构造方法 依赖注入描述了在容器中建…...

Web框架开发-Ajax

一、 Ajax准备知识:json 1、json(Javascript Obiect Notation,JS对象标记)是一种轻量级的数据交换格式 1 2 它基于 ECMAScript (w3c制定的js规范)的一个子集,采用完全独立于编程语言的文本格式来存储和表示数据。 简洁和清晰的层次结构使得 JSON 成为理想的数据交换语言。…...

Python爬虫之urllib库

1、urllib库的介绍 可以实现HTTP请求&#xff0c;我们要做的就是指定请求的URL、请求头、请求体等信息 urllib库包含如下四个模块 request&#xff1a;基本的HTTP请求模块&#xff0c;可以模拟请求的发送。error&#xff1a;异常处理模块。parse&#xff1a;工具模块&#x…...

Docker学习笔记 - 常用命令

目录 基本概念常用命令使用docker compose启动脚本创建自己的image Docker命令文档 1. 下载一个image 从hub.docker.com下载一个image。 docker pull [image name]下载时指定image的tag。 docker pull [image name]:<tag>举例&#xff0c;下载postgre的tag为alpine…...

数学建模(Topsis python代码 案例)

目录 介绍: 模板: 案例: 极小型指标转化为极大型(正向化): 中间型指标转为极大型(正向化): 区间型指标转为极大型(正向化): 标准化处理: 公式: Topsis(优劣解距离法): 公式: 完整代码: 结果: 介绍: 在数学建模中,Topsis方法是一种多准则决策分…...

gateway网关指定路由响应超时时间

gateway网关指定路由响应超时时间 spring:cloud:gateway:httpclient:responseTimeout: 10000这个配置用于设置HttpClient的响应超时时间&#xff0c;单位是毫秒。具体来说&#xff0c;这个配置表示当Gateway向后端服务发出请求后&#xff0c;如果在10秒内没有收到后端服务的响…...

docker 和K8S知识分享

docker知识&#xff1a; 比如写了个项目&#xff0c;并且在本地调试没有任务问题&#xff0c;这时候你想在另外一台电脑或者服务器运行&#xff0c;那么你需要在另外一台电脑或者服务器配置相同的软件&#xff0c;比如数据库&#xff0c;web服务器&#xff0c;必要的插件和库等…...

MySQL--select count(*)、count(1)、count(列名) 的区别你知道吗?

MySQL select count(*)、count(1)、count(列名) 的区别&#xff1f; 这里我们先给出正确结论&#xff1a; count(*)&#xff0c;包含了所有的列&#xff0c;会计算所有的行数&#xff0c;在统计结果时候&#xff0c;不会忽略列值为空的情况。count(1)&#xff0c;忽略所有的列…...

使用verilog设计实现16位CPU及仿真

这是一个简单的16位CPU(中央处理单元)的设计实验。这个CPU包括指令存储器、数据存储器、ALU(算术逻辑单元)、寄存器文件和控制单元。 设计一个简单的16位CPU的实验通常可以分为以下几个步骤: 指令集设计:首先确定CPU支持的指令集架构,包括指令格式、寄存器组织、地址模…...

Python将字符串转换为datetime

有这样一些字符串&#xff1a; 1710903685 20240320110125 2024-03-20 11:01:25 要转换成Python的datetime 代码如下&#xff1a; import functools import re from datetime import datetime, timedelta from typing import Union# pip install python-dateutil from date…...

Vue 3 + TypeScript + Vite的现代前端项目框架

随着前端开发技术的飞速发展&#xff0c;Vue 3、TypeScript 和 Vite 构成了现代前端开发的强大组合。这篇博客将指导你如何从零开始搭建一个使用Vue 3、TypeScript以及Vite的前端项目&#xff0c;帮助你快速启动一个性能卓越且类型安全的现代化Web应用。 Vue 3 是一款渐进式Jav…...

浏览器强缓存和弱缓存的主要区别

浏览器强缓存与弱缓存 浏览器的缓存机制主要分为两种&#xff1a;强缓存与协商缓存&#xff08;也称弱缓存&#xff09;。 强缓存 强缓存是指浏览器在请求一个资源时&#xff0c;不与服务器发生通信&#xff0c;直接从本地缓存中获取资源。如果存在有效的强缓存&#xff0c;…...

深度学习-2.9梯度不稳定和Glorot条件

梯度不稳定和Glorot条件 一、梯度消失和梯度爆炸 对于神经网络这个复杂系统来说&#xff0c;在模型训练过程中&#xff0c;一个最基础、同时也最常见的问题&#xff0c;就是梯度消失和梯度爆炸。 我们知道&#xff0c;神经网络在进行反向传播的过程中&#xff0c;各参数层的梯…...

地宫取宝dfs

分析&#xff1a; 矩阵里的每一个位置都有标记&#xff0c;要求的问题是&#xff1a;有几种方法能完成这个规定。 那么&#xff0c;我们只需要计算从开始(1,1)到最后(n,m)的深度优先搜索中&#xff0c;有几个是满足要求的即为正确答案。 有个要求是&#xff0c;如果一个格子中…...

Ollama 运行 Cohere 的 command-r 模型

Ollama 运行 Cohere 的 command-r 模型 0. 引言1. 安装 MSYS22. 安装 Golang3. Build Ollama4. 运行 command-r 0. 引言 Command-R Command-R 是一种大型语言模型&#xff0c;针对对话交互和长上下文任务进行了优化。它针对的是“可扩展”类别的模型&#xff0c;这些模型在高…...

2024年C语言最新经典面试题汇总(11-20)

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…...

arm linux应用程序crash分析一般方法

目录&#xff1a; 前言一、定位问题的基本方法论1.1 生产环境下系统崩溃的日志信息示例 二、 分析这类什么都没有的app crash的一般方法论&#xff1a;附录&#xff1a;附录1 pmap -p 进程PID 查看进程的内存分配情况附录2 cat /proc/pid/maps 总结 前言 linux的应用程序app开…...

Web安全防护技术解决方案

1、防止爆破 限制请求ip访问次数&#xff0c;超过设定访问次数后&#xff0c;拒绝访问或锁定N分钟后可再次请求 2、调用短信验证码时 加入验证码采用防爆破策略 3、上传后的文件防止被猜出爬取 保存在物理磁盘可进行加密防护文件不能存储在站点目录&#xff0c;防止通过ur…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...