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

【C++】位运算类题目总结

文章目录

  • 一. 位运算符脑图
  • 二. 相关题目
    • 1. 统计二进制数中0的个数
    • 2. 数组中只出现一次的数字
    • 3. 数组中只出现一次的数字 II
    • 4. 不用加减乘除做加法

一. 位运算符脑图

977ffc91b.png)

二. 相关题目

1. 统计二进制数中0的个数

解题思路:x &= (x-1);它的作用是每次循环把 x 的二进制中从右往左数的最后一位1变成0,直道变成全0为止,循环结束。
在这里插入图片描述

性能分析

  • 时间复杂度:O(1),一般输入的数字都有固定的二进制位数。
  • 空间复杂度:O(1),没有开辟额外的空间。

完整代码

size_t CountOne(int num)
{size_t count = 0;while(x){++count;// 通过这个迭代// 每次可以消除x二进制位中的一个1// 直到x最终为0x = x&(x-1);}return count;
}

2. 数组中只出现一次的数字

题目连接

解题思路

  1. 首先利用异或运算的规律:0异或任何数得到任何数,相同的数异或得0,用0去异或数组中的每一个元素,得到两个只出现一次的数字(我们假设是AB)异或在一起的结果。
  2. 这个结果的二进制中的1,表现的是A和B在这个比特位上的数字是不同的。我们就取从左往右第一个1所在的位数,假设是第3位,接着把原数组分成两组,分组标准是第3位是否为1。如此**,出现两次的数依然会被分到同一个组**,因为相同数字所有位都相同;而不同的数,肯定不在一组。然后把这两个组按照最开始的思路,拿数字0去依次异或,剩余的两个结果就是这两个只出现一次的数字。

性能分析

  • 时间复杂度:O(n)。n为数组的长度。
  • 空间复杂度:O(1)。

完整代码

class Solution 
{
public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {// 数组元素为0或输出型参数为空直接结束if(data.size() == 0 || num1 == nullptr || num2 == nullptr){return;}// 1、算出两个只出现一次的数字异或在一起的结果int ret = 0;for(const auto e : data){ret ^= e;}// 2、计算得到两个只出现一次的数字异或后最高比特位为1的位置int bit = 0;for(int i = 0; i < 32; ++i){if((ret>>i) & 1){bit = i;}}// 3、分成两组分别求出两个只出现一次的数字*num1 = 0;*num2 = 0;for(const auto e : data){if(e & (1<<bit)){*num1 ^= e;}else {*num2 ^= e;}}}
};

3. 数组中只出现一次的数字 II

题目连接

解题思路
首先如果我们不考虑这个只出现一次的数字,那么这个数组中的每一个数字都出现了三次。我们创建一个数组int count[32]去统计所有数的每一位比特位上一共有多少个1,统计结果 count 的每一个元素的值一定是 3n,如果把这个只出现一次的数字也给统计进去,那么 count 的每一个元素的值一定是3n 或 3n+1,根据 count 的每一个元素的值去模3,来还原出只那个出现一次的那个数字。

性能分析

  • 时间复杂度:O(n)。n为数组的长度。
  • 空间复杂度:O(1)。具体应该是数字的二进制位数,但一般输入的数字都有固定的二进制位数。

完整代码

class Solution {
public:int singleNumber(vector<int>& nums) {// 1、统计所有数的每一位比特位上一共有多少个1// 要么3n要么3n+1vector<int> count(32);for(auto& e : nums){for(int i=0; i<32; ++i)// 遍历每一个元素的每一位比特位{if(e & (1<<i)){++count[i];}}}// 2、根据count的结果还原出只出现一次的那个数字int ret=0;for(int i=0; i<32; ++i){if(count[i]%3){ret |= (1<<i);}}return ret;}
};

4. 不用加减乘除做加法

题目连接

解题思路

  • 二进制位异或运算相当于对应位相加,不考虑进位
    比如:
    1 ^ 1 = 0 —> 1 + 1 = 0 (当前位值为0,进一位)
    1 ^ 0 = 1 —> 1 + 0 = 1 (当前位值为1)
    0 ^ 0 = 0 —> 0 + 0 = 0 (当前位值为0)

  • 二进制位与运算相当于对应位相加之后的进位
    比如:
    1 & 1 = 1 —> 1 + 1 = 0 (当前位的值进一位)
    1 & 0 = 0 —> 1 + 0 = 1 (当前位的值不进位)
    0 & 0 = 0 —> 0 + 0 = 0 (当前位的值不进位)

  • 两个数相加:对应二进制位相加的结果 + 进位的结果
    比如:
    3 + 2 --> 0011 + 0010 --> 0011 ^ 0010 + ((0011 & 0010) << 1)
    —> (0011 ^ 0010) ^ ((0011 & 0010) << 1), 当进位之后的结果为0时,相加结束

完整代码

class Solution {
public:int add(int a, int b) {// 进位数为0时,结束循环while(b){// 得到二者和的无进位的结果int notCarry=a^b;// 得到进位数*10的结果b=((unsigned int)(a&b))*2;a=notCarry;}return a;}
};

相关文章:

【C++】位运算类题目总结

文章目录 一. 位运算符脑图二. 相关题目1. 统计二进制数中0的个数2. 数组中只出现一次的数字3. 数组中只出现一次的数字 II4. 不用加减乘除做加法 一. 位运算符脑图 二. 相关题目 1. 统计二进制数中0的个数 解题思路&#xff1a;x & (x-1)&#xff1b;它的作用是每次循环…...

Node服务端开发【NPM】

文章目录 前言NPM使用NPM使用场景NPM的常用命令NPM命令使用介绍使用NPM安装模块下载三方包全局安装VS本地安装本地安装全局安装全局模块路径查看与路径修改 卸载模块更新模块搜索模块NPM服务器发布包 NPM换源nrm全局安装 nrm:nrm ls 列出来现在已经配置好的所有的原地址nrm use…...

Doris(21):Doris的函数—日期函数

1 CONVERT_TZ(DATETIME dt, VARCHAR from_tz, VARCHAR to_tz) 转换datetime值dt,从 from_tz 由给定转到 to_tz 时区给出的时区,并返回的结果值。 如果参数无效该函数返回NULL。 select convert_tz(2019-08-01 13:21:03, Asia/Shanghai, America/Los_Angeles); select co…...

和月薪5W的阿里程序员聊过后,才知道自己一直在打杂...

前几天和一个朋友聊面试&#xff0c;他说上个月同时拿到了腾讯和阿里的offer&#xff0c;最后选择了阿里。 阿里内部将员工一共分为了14个等级&#xff0c;P6是资深工程师&#xff0c;P7是技术专家。 其中P6和P7就是一个分水岭了&#xff0c;P6是最接近P7的不持股员工&#x…...

西门子PLC沿脉冲类指令汇总

S7-1200CPU提供了四种沿脉冲指令供用户使用&#xff0c;分别为&#xff1a;扫描操作数信号边沿指令、在信号边沿置位操作数的指令、扫描RLO的信号边沿指令以及检测信号边沿指令。 信号从0--1的时刻称为上升沿&#xff0c;信号从1--0的时刻称为下降沿&#xff0c;不管是上升沿还…...

软件多语言文案脚本自动化方案

开发高效提速系列目录 软件多语言文案脚本自动化方案 软件多语言文案脚本自动化方案 背景目标整体方案1. 创建文案资源文件2. python脚本开发3. Python脚本执行与管理4. 人员职责分配 PyCharm使用说明1. PyCharm下载2. PyCharm安装配置3. 异常情况解决 总结 博客创建时间&…...

C++017-C++文件读写应用

文章目录 C017-C文件读写应用C文件读写应用CSP-J目标1. 文件的基本概念、文本文件的基本操作2.文本文件类型与二进制文件类型文本文件类型二进制文件类型二进制查看工具 3.文件重定向、文件读写等操作关闭文件文件操作-写入文本文件文件操作-读取文本文件文件操作-写入二进制文…...

计算机网络 实验二

⭐计网实验专栏&#xff0c;欢迎订阅与关注&#xff01; ★观前提示&#xff1a;本篇内容为计算机网络实验。内容可能会不符合每个人实验的要求&#xff0c;因此以下内容建议仅做思路参考。 一、实验目的 &#xff08;1&#xff09;掌握IP地址的基本结构(网络部分与主机部分的…...

Unity 3D 学习笔记(1)

文章目录 1.Unity 3D 概述2.Unity的安装过程3.Unity 3D 的项目管理4.Unity 3D 中的场景5.Unity 3D 的界面组成 1.Unity 3D 概述 Unity 3D简介&#xff1a;Unity 3D是虚拟现实行业中使用率较高的一款开发引擎&#xff0c;由Unity Technology公司开发。通过Unity&#xff0c;开发…...

P1050 [NOIP2005 普及组] 循环

题目描述 乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天&#xff0c;他突然对数的正整数次幂产生了兴趣。 众所周知&#xff0c;22 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6…2,4,8,6,2,4,8,6… 我们说 22 的正整数次幂最后一位的循环长度…...

软考算法-排序篇-上

数据排序 一&#xff1a;故事背景二&#xff1a;直接插入排序2.1 概念2.2 画图表示2.3 代码实现2.4 总结提升 三&#xff1a;希尔排序3.1 概念3.2 画图表示3.3 代码实现3.4 总结提升 四&#xff1a;直接选择排序4.1 概念4.2 画图表示4.3 代码实现4.4 总结提升 五&#xff1a;堆…...

总结836

学习目标&#xff1a; 4月&#xff08;复习完高数18讲内容&#xff0c;背诵21篇短文&#xff0c;熟词僻义300词基础词&#xff09; 学习内容&#xff1a; 暴力英语&#xff1a;背诵《keep your direction》&#xff0c;默写&#xff0c;英语语法 高等数学&#xff1a;刷题&a…...

ginbuilder 工具快速创建

ginbuilder github 地址 快速创建一个ginweb项目&#xff1a; 目前apps下只有http服务&#xff0c;如果后续有需要的话&#xff0c;会添加上rpc服务&#xff0c;websocket服务后边如果有需要会添加上swagger 创建完成的目录结构 ├── apps │ ├── apis // 所有的apis…...

【Java基础面试宝典】堆、栈、方法区分别都存储了那些内容?wait 和 sleep 方法的区别?

目录 堆、栈、方法区分别都存储了那些内容&#xff1f; 堆&#xff08;heap&#xff09; 栈&#xff08;stack&#xff09; 方法区&#xff08;method&#xff09; 在 java 中 wait 和 sleep 方法的区别&#xff1f; 堆、栈、方法区分别都存储了那些内容&#xff1f; 堆&a…...

古剑飞仙手游Linux系统服务器架设教程

安装宝塔直接运行命令即可。 yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh 搭建环境&#xff1a; centos 7以上系统服务器 宝塔面板安装应用如下&#xff1a; Nginx1.14 mysql5.7 php5.6 1…...

python实战应用讲解-【numpy数组篇】常用函数(十)(附python示例代码)

目录 Python Numpy MaskedArray.ravel()函数 Python Numpy MaskedArray.reshape()函数 Python Numpy MaskedArray.resize()函数 Python Numpy MaskedArray.std()函数 Python Numpy MaskedArray.sum()函数 Python Numpy MaskedArray.swapaxes()函数 Python Numpy MaskedA…...

计算机组成原理(考研408)练习题#2

用于复习408或计算机组成原理期末考试。如有错误请在评论区指出。 So lets start studying with questions! それでは、問題の勉強を始めましょう&#xff01; 11.某 cache 采用全相联映射&#xff0c;假设 cache 有 3 块&#xff0c;程序运行过程中需要访问的主存块号依 次为…...

Apache POI,springboot中导出excel报表

2. Apache POI 2.1 介绍 Apache POI 是一个处理Miscrosoft Office各种文件格式的开源项目。简单来说就是&#xff0c;我们可以使用 POI 在 Java 程序中对Miscrosoft Office各种文件进行读写操作。 一般情况下&#xff0c;POI 都是用于操作 Excel 文件。 Apache POI 的应用场景…...

CSS(一)-- 三种样式表

目录 1. 行内样式表 2. 内部样式表 3. 外部样式表&#xff08;即引入 .css文件&#xff09;&#xff08;重点掌握&#xff09; 1. 行内样式表 行内样式表&#xff08;内联样式表&#xff09;是在元素标签内部的 style 属性中设定 CSS 样式。适合于修改简单样式。 <di…...

嵌入式之Samba服务器搭建

在嵌入式系统开发应用平台中&#xff0c;tftp、nfs和samba服务器是最常用的文件传输工具 tftp和nfs是在嵌入式Linux开发环境中经常使用的传输工具 samba则是Linux和Windows之间的文件传输工具。 下面演示在linux上搭建Samba服务器 sudo apt-get install samba chmod -R 77…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...