Leetcode 191.位1的个数

 

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

提示:

  • 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
  • 在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在 示例 3 中,输入表示有符号整数 -3

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 输入必须是长度为 32 的 二进制串 。

进阶

  • 如果多次调用这个函数,你将如何优化你的算法?

我的答案:

一、信息

1.输入是一个二进制无符号整数

2.返回'1'的个数

二、分析

条件1告诉我输入的数据类型是无符号整型

条件2告诉我此次编程的目标

三、步骤

遇到问题

1.如何计算位数? 

四、实现 

我的答案:

毫无思路

这是一个常见的面试问题。让我们首先为这个问题创建一个C语言的解决方案,然后是一个C++的解决方案。

#include <stdint.h> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {count += n & 1;n >>= 1;}return count;
}

C++:

#include <cstdint> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {count += n & 1;n >>= 1;}return count;
}

进阶:优化算法

如果要多次调用这个函数,我们可以使用Brian Kernighan的算法,它可以更快地计算二进制中1的个数,它的工作原理是每次迭代都去掉最右边的1,直到所有的1都被去掉。

C语言(进阶)

#include <stdint.h> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {n &= (n - 1);count++;}return count;
}

C++(进阶)

#include <cstdint> // for uint32_tint hammingWeight(uint32_t n) {int count = 0;while (n) {n &= (n - 1);count++;}return count;
}

Brian Kernighan的算法的效率是O(k),其中k是二进制数中1的个数,因此对于具有少量1的数字,它的效率非常高。

Leetcode答案

方法一:循环检查二进制位
思路及解法

我们可以直接循环检查给定整数 nnn 的二进制位的每一位是否为 111。

具体代码中,当检查第 iii 位时,我们可以让 nnn 与 2i2^i2 
i
  进行与运算,当且仅当 nnn 的第 iii 位为 111 时,运算结果不为 000。

代码
C++

class Solution {
public:int hammingWeight(uint32_t n) {int ret = 0;for (int i = 0; i < 32; i++) {if (n & (1 << i)) {ret++;}}return ret;}
};


复杂度分析

时间复杂度:O(k)O(k)O(k),其中 kkk 是 int\texttt{int}int 型的二进制位数,k=32k=32k=32。我们需要检查 nnn 的二进制位的每一位,一共需要检查 323232 位。

空间复杂度:O(1)O(1)O(1),我们只需要常数的空间保存若干变量。

方法二:位运算优化
思路及解法

观察这个运算:n & (n−1)n~\&~(n - 1)n & (n−1),其运算结果恰为把 nnn 的二进制位中的最低位的 111 变为 000 之后的结果。

如:6 & (6−1)=4,6=(110)2,4=(100)26~\&~(6-1) = 4, 6 = (110)_2, 4 = (100)_26 & (6−1)=4,6=(110) 
2

 ,4=(100) 
2

 ,运算结果 444 即为把 666 的二进制位中的最低位的 111 变为 000 之后的结果。

这样我们可以利用这个位运算的性质加速我们的检查过程,在实际代码中,我们不断让当前的 nnn 与 n−1n - 1n−1 做与运算,直到 nnn 变为 000 即可。因为每次运算会使得 nnn 的最低位的 111 被翻转,因此运算次数就等于 nnn 的二进制位中 111 的个数。

代码

C++
Java
Python3
Golang
JavaScript
C

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


复杂度分析

时间复杂度:O(log⁡n)O(\log n)O(logn)。循环次数等于 nnn 的二进制位中 111 的个数,最坏情况下 nnn 的二进制位全部为 111。我们需要循环 log⁡n\log nlogn 次。

空间复杂度:O(1)O(1)O(1),我们只需要常数的空间保存若干变量。
链接:https://leetcode.cn/problems/number-of-1-bits/solutions/672082/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源:力扣(LeetCode)
英雄师傅答案:

int hammingWeight(uint32_t n){int c=0;while(n){if(n&1){++c;}n>>=1;}return c;
}

几种方法的比较:

我的方法

1. **Brian Kernighan算法:** 这实际上与你给出的第二种方法相同,即使用`n & (n-1)`技巧。它直接移除了数字中最右侧的'1'。

2. **直接计数:** 这是一个直观的方法。对数字的每一位进行循环,并用`n & 1`检查最低位是否为'1'。之后,右移数字。

### 对比与分析

**1. 循环检查二进制位 vs 直接计数**
- **思路相似性:** 这两种方法都是基于检查每一位来计算'1'的数量。
- **优势:** 这两种方法都是非常直观的。对于初学者或者希望代码具有更高可读性的情境,它们都很适用。
- **劣势:** 它们的性能可能不如位运算优化方法,特别是当原始数字的二进制表示中有较少的'1'时。

**2. 位运算优化 vs Brian Kernighan算法**
- **思路相似性:** 它们实际上是同一种方法。都使用了`n & (n-1)`的技巧来移除数字中的一个'1'。
- **优势:** 它们都比直接计数方法快,尤其是在数字中'1'较少时。
- **劣势:** 对于不熟悉这种特定位运算的人来说,可能不够直观。

### 总结

- 我的"直接计数"方法和你给的"循环检查二进制位"方法非常相似。它们都是基于检查每一位的简单方法。然而,由于涉及到的位移操作,实现的细节可能会有所不同。
  
- 我的"Brian Kernighan算法"和你给的"位运算优化"方法实际上是同一种方法。这种方法利用了`n & (n-1)`来高效地计算'1'的数量,它比基于逐位检查的方法更快。

无论选择哪种方法,最重要的是理解其背后的逻辑和原理,这样在遇到不同的问题时,你可以灵活地应用和调整这些方法。

总结:

一、发现的不足。

1.运算符>>知识点尤其是移位运算不熟悉

2.

二、学到什么?

从这道题目中,我们可以学到以下几点:

1. **二进制基础**:题目加深了我们对二进制数的理解,特别是如何操作和解读32位无符号整数的二进制形式。

2. **位操作**:题目展示了如何使用位操作符,特别是`&` (位与) 和 `<<` (左移)。位操作是计算机科学中的一个重要概念,特别是在低级编程、嵌入式系统和性能关键应用中。

3. **算法优化**:通过比较两种方法,我们看到了如何从一个直接的算法优化到一个更高效的算法。方法一直接检查每一位,而方法二使用了一个巧妙的技巧,即`n & (n - 1)`,来迅速定位并清除最右侧的`1`。这显示了算法和数据结构知识的重要性,特别是如何使用基础的位操作来优化算法。

4. **代码简洁性和效率**:两种方法都提供了解决同一问题的有效方法,但它们之间的效率有所不同。这强调了在解决问题时不仅要考虑解决方案的正确性,还要考虑其效率。

5. **问题分析与解决策略**:面对一个问题时,首先需要理解其背后的概念和要求,然后尝试提出不同的策略或方法。对于同一个问题,可能存在多种有效的解决策略,但它们在实际应用中的效率可能会有所不同。

6. **细节注意**:在处理位操作时,特别要注意边界条件和位数。例如,对于32位的整数,当我们移动超过32位时,需要注意可能出现的行为。

综上所述,这道题目为我们提供了一个很好的机会,来学习和实践位操作、算法优化和问题解决策略。

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/110221.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

java+springboot+mysql农业园区管理系统

项目介绍&#xff1a; 使用javaspringbootmysql开发的农业园区管理系统&#xff0c;系统包含超级管理员、管理员、用户角色&#xff0c;功能如下&#xff1a; 超级管理员&#xff1a;管理员管理&#xff1b;用户管理&#xff1b;土地管理&#xff08;租赁&#xff09;&#x…

语言模型(language model)

文章目录 引言1. 什么是语言模型2. 语言模型的主要用途2.1 言模型-语音识别2.2 语言模型-手写识别2.3 语言模型-输入法 3. 语言模型的分类4. N-gram语言模型4.1 N-gram语言模型-平滑方法4.2 ngram代码4.3 语言模型的评价指标4.4 两类语言模型的对比 5. 神经网络语言模型6. 语言…

RabbitMQ的镜像队列

镜像队列 如果 RabbitMQ 集群中只有一个 Broker 节点&#xff0c;那么该节点的失效将导致整体服务的临时性不可用&#xff0c;并且也可能会导致消息的丢失。可以将所有消息都设置为持久化&#xff0c;并且对应队列的durable 属性也设置为 true &#xff0c;但是这样仍然无法…

基于java swing和mysql实现的汽车租赁管理系统(源码+数据库+文档+运行指导视频)

一、项目简介 本项目是一套基于java swing和mysql实现的汽车租赁管理系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、项目文档、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经…

计算机竞赛 基于YOLO实现的口罩佩戴检测 - python opemcv 深度学习

文章目录 0 前言1 课题介绍2 算法原理2.1 算法简介2.2 网络架构 3 关键代码4 数据集4.1 安装4.2 打开4.3 选择yolo标注格式4.4 打标签4.5 保存 5 训练6 实现效果6.1 pyqt实现简单GUI6.3 视频识别效果6.4 摄像头实时识别 7 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xf…

打架斗殴监测识别算法 yolov8

打架斗殴监测识别算法采用yolov8先进的图像处理和机器学习算法框架模型&#xff0c;打架斗殴监测识别算法能够自动识别和分析出打架斗殴的行为特征。一旦系统检测到打架斗殴行为&#xff0c;将自动触发告警。YOLO的结构非常简单&#xff0c;就是单纯的卷积、池化最后加了两层全…

抢先体验|乐鑫推出 ESP32-S3-BOX-3 新一代开源 AIoT 开发套件

乐鑫科技 (688018.SH) 非常高兴地宣布其开发套件阵容的最新成员 ESP32-S3-BOX-3。这款完全开源的 AIoT 应用开发套件搭载乐鑫高性能 ESP32-S3 AI SoC&#xff0c;旨在突破传统开发板&#xff0c;成为新一代开发工具的引领者。 【乐鑫新品抢先体验】ESP32-S3-BOX-3 新一代开源 A…

文件上传漏洞之条件竞争

这里拿upload-labs的第18关做演示 首先先看代码 $is_upload false; $msg null;if(isset($_POST[submit])){$ext_arr array(jpg,png,gif);$file_name $_FILES[upload_file][name];$temp_file $_FILES[upload_file][tmp_name];$file_ext substr($file_name,strrpos($file_…

AES+base64+远程加载----ConsoleApplication811项目

ConsoleApplication9.cpp // ConsoleApplication9.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 //#include <iostream> #include <Windows.h> #include <wininet.h> #include "base64.h" #include "AES.h" …

【Rust】Rust学习 第十九章高级特征

现在我们已经学习了 Rust 编程语言中最常用的部分。在第二十章开始另一个新项目之前&#xff0c;让我们聊聊一些总有一天你会遇上的部分内容。你可以将本章作为不经意间遇到未知的内容时的参考。本章将要学习的功能在一些非常特定的场景下很有用处。虽然很少会碰到它们&#xf…

Redis进阶 - Lua语法

原文首更地址&#xff0c;阅读效果更佳&#xff01; Redis进阶 - Lua语法 | CoderMast编程桅杆https://www.codermast.com/database/redis/redis-advance-lua-language.html 初识 Lua Lua 是一种轻量小巧的脚本语言&#xff0c;用标准的 C 语言编写并以源代码形式开放&#…

闲人闲谈PS之四十六——网络生产全流程

惯例闲话&#xff1a;下半年已开始块行情似乎又是一波大涨&#xff0c;很多朋友委托我介绍PS顾问&#xff0c;很多朋友已经上了能源系统项目&#xff0c;这就造成装备制造的PS又是极度紧缺&#xff0c;rate也还可以&#xff0c;搞的自己也有点心痒痒。这种逆势大涨&#xff0c;…

Django(8)-静态资源引用CSS和图片

除了服务端生成的 HTML 以外&#xff0c;网络应用通常需要一些额外的文件——比如图片&#xff0c;脚本和样式表——来帮助渲染网络页面。在 Django 中&#xff0c;我们把这些文件统称为“静态文件”。 我们使用static文件来存放静态资源&#xff0c;django会在每个 INSTALLED…

ReoGrid.NET集成到winfrom

ReoGrid一个支持excel操作的控件,支持集成到任何winfrom项目内。 先看效果图: 如何使用&#xff1a; 使用ReoGrid自带excel模版设计工具先设计一个模版,设计器如下&#xff1a; 具体例子看官方文档 代码示例如下&#xff1a; var sheet reoGridControl1.CurrentWorksheet; …

从C语言到C++_34(C++11_下)可变参数+ lambda+function+bind+笔试题

目录 1. 可变参数模板 1.1 展开参数包 1.1.1 递归函数方式展开 1.1.2 逗号表达式展开 1.2 emplace相关接口 2. lambda表达式&#xff08;匿名函数&#xff09; 2.1 C11之前函数的缺陷 2.2 lambda表达式语法 2.3 函数对象与lambda表达式 3. 包装器 3.1 function包装器…

华为云服务器前后端分离项目打包上传及nginx配置

目录 1、Spring Boot项目打包 2、后端上传到云服务器 3、前端打包 1&#xff09;前端请求路径修改 2&#xff09;打包上传 4、下载nginx 1&#xff09;添加源 2&#xff09;安装Nginx 3&#xff09;查看nginx安装目录和版本 4&#xff09;启动 重启nginx命令 5&#…

Midjourney学习(一)prompt的基础

prompt目录 sd和mj的比较prompt组成风格表现风格时代描述表情色彩情绪环境 sd和mj的比较 自从去年9月份开始&#xff0c;sd就变得非常或火&#xff0c;跟它一起的还有一个midjourney。 他们就像是程序界的两种模式&#xff0c;sd是开源的&#xff0c;有更多的可能性更可控。但是…

嵌入式学习笔记——ARM的编程模式和7种工作模式

ARM提供的指令集 ARM态-ARM指令集&#xff08;32-bit&#xff09; Thumb态-Thumb指令集&#xff08;16-bit&#xff09; Thumb2态-Thumb2指令集&#xff08;16 & 32 bit&#xff09; Thumb指令集是对ARM指令集的一个子集重新编码得到的&#xff0c;指令长度为16位。通常在…

windows系统配置tcp最大连接数

打开注册表 运行->regedit HKLM\SYSTEM\CurrentControlSet\Services\Tcpip\Parameters目录下 增加一个MaxUserPort&#xff08;默认值是5000&#xff0c;端口范围是1025至5000&#xff09;MaxUserPort设置为65534&#xff08;需重启服务器&#xff09; 执行dos命令&…

克服紧张情绪:程序员面试心理准备的关键

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…