当前位置: 首页 > 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;并可在噪声的空间数据库中发现任意形…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

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

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

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...