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

大一计算机的自学总结:位运算的应用及位图

前言

不仅异或运算有很多骚操作,位运算本身也有很多骚操作。(尤其后几个题,太逆天了)

一、2 的幂

class Solution {
public:bool isPowerOfTwo(int n) {return n>0&&n==(n&-n);}
};

 根据二进制表示数的原理,2的幂的二进制只有1个1,所以根据Brian算法取最右侧的1,只要n等于取完最右侧1的数,即为2的幂。

二、3 的幂

class Solution {
public:bool isPowerOfThree(int n) {return n>0&&1162261467%n==0;}
};

 1162261467就是整型范围内3的幂的最大值,所以只要n能整除它,就说明n为3的幂。

三、数字范围按位与

class Solution {
public:int rangeBitwiseAnd(int left, int right) {while(left<right){right-=right&(-right);}return right;}
};

 思考与运算的性质,只要有0就是0,又想到连续的区间内,相邻两个数的最右侧1的那位必然不同,所以与运算后最右侧的1必然留不下,所以只要在大于左侧的范围内,每次减去取完最右侧1的数即可。

这么说肯定很抽象很难理解,比如right为0101001101,则right-1为0101001100,所以与运算后最右侧的1肯定留不下,所以减去1,right为0101001100,此时right-1为0101001011,所以第三位的1也留不下,所以right要减去2的平方,成为0101001000,之后若right大于left就继续循环。

四、颠倒二进制位

class Solution {
public:uint32_t reverseBits(uint32_t n) {n=((n&0xaaaaaaaa)>>1)|((n&0x55555555)<<1);n=((n&0xcccccccc)>>2)|((n&0x33333333)<<2);n=((n&0xf0f0f0f0)>>4)|((n&0x0f0f0f0f)<<4);n=((n&0xff00ff00)>>8)|((n&0x00ff00ff)<<8);n=(n>>16)|(n<<16);return n;}
};

 这个和下一个题的思路太过于逆天了。

简单说,就是每次以1,2,48,16为单位进行逆序。例如,abcdefgh先以1为单位逆序成badcfehg;再以2为单位逆序成dcbahgfe;再以4为单位逆序成hgfedcba。

具体原理就是这样,实现起来就是先让abcdefgh&10101010成为a0c0e0g0,再让abcdefgh&01010101成为0b0d0f0h,之后让第一个数右移1位第二个数左移1位,最后或运算就是badcfehg。而10101010就是十六进制aa,01010101就是十六进制55。

之后递推就行。(累)

五、汉明距离

class Solution {
public:int hammingDistance(int x, int y) {return cntOnes(x^y);}int cntOnes(int n){n=(n&0x55555555)+((n>>1)&0x55555555);n=(n&0x33333333)+((n>>2)&0x33333333);n=(n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);n=(n&0x00ff00ff)+((n>>8)&0x00ff00ff);n=(n&0x0000ffff)+((n>>16)&0x0000ffff);return n;}
};

 这个的思路和上一个题差不多。

比如,11111001,先保留奇数位的信息,&01010101得到01010001;再获取偶数位的信息,让11111001右移1位后&01010101,得到01010100;最后让两数相加得到10100101,表示从左到右,前两位中有两个1,往后两位2个,之后1个,最后两位1个1。

之后以此类推。

六、位图

1.原理

一般来说,如果要记录出现过的数字,我们一般会向数组中输入这个数表示这个数出现过。但这样的话每个数字都会占用一个int的内存。所以,为了进一步节省内存,就可以使用位图。位图就是在一个位置上,通过这个数32位的二进制,用0和1分别表示出现与否,用位数0~31表示数字0~31。这样的话,一个int的位置就可以表示32个数字。

2.实现——设计位集

class Bitset {vector<int>bitset;bool reverse;int ones;int zeros;int n;public:Bitset(int size) {for(int i=0;i<size;i++){bitset.push_back(0);}reverse=false;ones=0;zeros=size;n=size;}void fix(int idx) {if(!reverse){if((bitset[idx/32]&(1<<(idx%32)))==0){zeros--;ones++;bitset[idx/32]|=(1<<(idx%32));}}else{if((bitset[idx/32]&(1<<(idx%32)))!=0){zeros--;ones++;bitset[idx/32]^=(1<<(idx%32));}}}void unfix(int idx) {if(!reverse){if((bitset[idx/32]&(1<<(idx%32)))!=0){zeros++;ones--;bitset[idx/32]^=(1<<(idx%32));}}else{if((bitset[idx/32]&(1<<(idx%32)))==0){zeros++;ones--;bitset[idx/32]|=(1<<(idx%32));}}}void flip() {reverse=!reverse;int t=ones;ones=zeros;zeros=t;}bool all() {return ones==n;}bool one() {return ones>0;}int count() {return ones;}string toString() {string s;for(int i=0,num;i<n;i++){num=(bitset[i/32]&(1<<(i%32)))==0?0:1;num^=(reverse?1:0);s+=num+'0';}return s;}
};

 重点是全局变量ones和zeros以及reverse,用来记录0和1的数量以及是否经历反转。

在加入中,若没反转过,即0表示没有,1表示有。那么若该位为0,则或运算成为1,并同步让zeros--,ones++。之后反转过的和删除思路相似。

之后反转函数只要将reverse取反,然后交换zeros和ones。

判断是否全为1、判断是否存在1和计算1的数量函数只要对ones操作即可。

转成字符串函数,按位的数量遍历,每次取出该位的数num,若经过反转,则反转num。

总结

位运算这几个例题的思路一个比一个逆天,一个比一个抽象,但用出来确实很nb。(晕)

END

相关文章:

大一计算机的自学总结:位运算的应用及位图

前言 不仅异或运算有很多骚操作&#xff0c;位运算本身也有很多骚操作。&#xff08;尤其后几个题&#xff0c;太逆天了&#xff09; 一、2 的幂 class Solution { public:bool isPowerOfTwo(int n) {return n>0&&n(n&-n);} }; 根据二进制表示数的原理&#…...

计算机毕业设计Django+Tensorflow音乐推荐系统 机器学习 深度学习 音乐可视化 音乐爬虫 知识图谱 混合神经网络推荐算法 大数据毕设

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…...

AI 图片涌入百度图库

在这个信息爆炸的时代&#xff0c;我们习惯了通过搜索引擎来获取各种想要的信息和图片。然而&#xff0c;现在打开搜索引擎看到的却是许多真假难辨的信息——AI图片&#xff0c;这部分数据正以惊人的速度涌入百度图库&#xff0c;让小编不禁想问&#xff1a;未来打开百度图库不…...

可爱狗狗的404动画页面HTML源码

源码介绍 可爱狗狗的404动画页面HTML源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果 效果预览 源码获取 可爱狗狗的404动画页面HTML源码...

【微服务与分布式实践】探索 Dubbo

核心组件 服务注册与发现原理 服务提供者启动时&#xff0c;会将其服务信息&#xff08;如服务名、版本、所在节点的网络地址等&#xff09;注册到注册中心。服务消费者则可以从注册中心发现可用的服务提供者列表&#xff0c;并与之通信。注册中心会存储服务的信息&#xff0c…...

OpenCSG月度更新2025.1

1月的OpenCSG取得了一些亮眼的成绩 在2025年1月&#xff0c;OpenCSG在产品和社区方面继续取得了显著进展。产品方面&#xff0c;推出了AutoHub浏览器自动化助手&#xff0c;帮助用户提升浏览体验&#xff1b;CSGHub企业版功能全面升级&#xff0c;现已开放试用申请&#xff0c…...

C++封装红黑树实现mymap和myset和模拟实现详解

文章目录 map和set的封装map和set的底层 map和set的模拟实现insertiterator实现的思路operatoroperator- -operator[ ] map和set的封装 介绍map和set的底层实现 map和set的底层 一份模版实例化出key的rb_tree和pair<k,v>的rb_tree rb_tree的Key和Value不是我们之前传统意…...

二次封装的方法

二次封装 我们开发中经常需要封装一些第三方组件&#xff0c;那么父组件应该怎么传值&#xff0c;怎么调用封装好的组件原有的属性、插槽、方法&#xff0c;一个个调用虽然可行&#xff0c;但十分麻烦&#xff0c;我们一起来看更简便的方法。 二次封装组件&#xff0c;属性怎…...

消息队列篇--通信协议篇--网络通信模型(OSI7层参考模型,TCP/IP分层模型)

一、OSI参考模型&#xff08;Open Systems Interconnection Model&#xff09; OSI参考模型是一个用于描述和标准化网络通信功能的七层框架。它由国际标准化组织&#xff08;ISO&#xff09;提出&#xff0c;旨在为不同的网络设备和协议提供一个通用的语言和结构&#xff0c;以…...

Python实现U盘数据自动拷贝

功能&#xff1a;当电脑上有U盘插入时&#xff0c;自动复制U盘内的所有内容 主要特点&#xff1a; 1、使用PyQt5创建图形界面&#xff0c;但默认隐藏 2、通过CtrlAltU组合键可以显示/隐藏界面 3、自动添加到Windows启动项 4、监控USB设备插入 5、按修改时间排序复制文件 6、静…...

汇编的使用总结

一、汇编的组成 1、汇编指令&#xff08;指令集&#xff09; 数据处理指令: 数据搬移指令 数据移位指令 位运算指令 算术运算指令 比较指令 跳转指令 内存读写指令 状态寄存器传送指令 异常产生指令等 2、伪指令 不是汇编指令&#xff0c;但是可以起到指令的作用&#xff0c;伪…...

DeepSeek理解概率的能力

问题&#xff1a; 下一个问题是概率问题。乘车时有一个人带刀子的概率是百分之一&#xff0c;两个人同时带刀子的概率是万分之一。有人认为如果他乘车时带上刀子&#xff0c;那么还有其他人带刀子的概率就是万分之一&#xff0c;他乘车就会安全得多。他的想法对吗&#xff1f;…...

AI 浪潮席卷中国年,开启科技新春新纪元

在这博主提前祝大家蛇年快乐呀&#xff01;&#xff01;&#xff01; 随着人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;其影响力已经渗透到社会生活的方方面面。在中国传统节日 —— 春节期间&#xff0c;AI 技术也展现出了巨大的潜力&#xff0c;为中国年带…...

AI时代的网络安全:传统技术的落寞与新机遇

AI时代的网络安全&#xff1a;传统技术的落寞与新机遇 在AI技术飞速发展的浪潮中&#xff0c;网络安全领域正经历着前所未有的变革。一方面&#xff0c;传统网络安全技术在面对新型攻击手段时逐渐显露出局限性&#xff1b;另一方面&#xff0c;AI为网络安全带来了新的机遇&…...

可以称之为“yyds”的物联网开源框架有哪几个?

有了物联网的发展&#xff0c;我们的生活似乎也变得更加“鲜活”、有趣、便捷&#xff0c;包具有科技感的。在物联网&#xff08;IoT&#xff09;领域中&#xff0c;也有许多优秀的开源框架支持设备连接、数据处理、云服务等&#xff0c;成为被用户们广泛认可的存在。以下给大家…...

线程局部存储tls的原理和使用

一、背景 tls即Thread Local Storage&#xff0c;也就是线程局部存储&#xff0c;可在进程内&#xff0c;多线程按照各个线程分开进行存储。对于一些与线程上下文相关的变量&#xff0c;可放到tls中&#xff0c;减少多线程之间的数据同步的开销。 有人可能会问&#xff0c;我…...

RK3588平台开发系列讲解(ARM篇)ARM64底层中断处理

文章目录 一、异常级别二、异常分类2.1、同步异常2.2、异步异常三、中断向量表沉淀、分享、成长,让自己和他人都能有所收获!😄 一、异常级别 ARM64处理器确实定义了4个异常级别(Exception Levels, EL),分别是EL0到EL3。这些级别用于管理处理器的特权级别和权限,级别越高…...

CAN总线

1. 数据帧&#xff08;Data Frame&#xff09; 数据帧是 CAN 总线中最常用的帧类型&#xff0c;用于传输实际的数据。其结构如下&#xff1a; 起始位&#xff08;Start of Frame, SOF&#xff09;&#xff1a;标志帧的开始。标识符&#xff08;Identifier&#xff09;&#x…...

qwen2.5-vl:阿里开源超强多模态大模型(包含使用方法、微调方法介绍)

1.简介 在 Qwen2-VL 发布后的五个月里&#xff0c;众多开发者基于该视觉语言模型开发了新的模型&#xff0c;并向 Qwen 团队提供了极具价值的反馈。在此期间&#xff0c;Qwen 团队始终致力于打造更具实用性的视觉语言模型。今天&#xff0c;Qwen 家族的最新成员——Qwen2.5-VL…...

python实现dbscan

python实现dbscan 原理 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。它将簇定义为密度相连的点的最大集合&#xff0c;能够把具有足够高密度的区域划分为簇&#xff0c;并可在噪声的空间数据库中发现任意形…...

JavaSec-RCE

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

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...