首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
人狠话不多的六边形战士很想去东北泡澡
西安电子科技大学 电子信息类
发布于北京
关注
已关注
取消关注
@牛客题解官:
二进制中1的个数
题目的主要信息:统计32位整型有符号数二进制中1的个数因负数用补码表示,故不能用连除法举一反三:学习完本题的思路你可以解决如下题目:JZ64. 求1+2+3+...+nJZ65. 不用加减乘除做加法方法一:循环按位比较法(推荐使用)知识点:位运算计算机的数字由二进制表示,我们平常的运算是对整个数字进行运算,但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。思路:我们可以检查该数字的二进制每一位是否为1,如果遍历二进制每一位呢?可以考虑移位运算,每次移动一位就可以。至于怎么统计到1呢?我们都只知道数字1与数字相位与运算,其实只是最后一位为1就是1,最后一位为0就是0,这样我们只需要将数字1移位运算,就可以遍历二进制的每一位,再去做位与运算,结果为1的就是二进制中为1的。具体做法:step 1:遍历二进制的32位,通过移位0-31次实现。step 2:将移位后的1与数字进行位与运算,结果为1就记录一次。Java实现代码:public class Solution { public int NumberOf1(int n) { int res = 0; //遍历32位 for(int i = 0; i < 32; i++){ //按位比较 if((n & (1 << i)) != 0) res++; } return res; }}C++实现代码:class Solution {public: int NumberOf1(int n) { int res = 0; //遍历32位 for(int i = 0; i < 32; i++){ //按位比较 if((n & (1 << i)) != 0) res++; } return res; }};Python实现代码:class Solution: def NumberOf1(self , n: int) -> int: res = 0 #遍历32位 for i in range(32): #按位比较 if (n & (1 << i)) != 0: res += 1 return res复杂度分析:时间复杂度:O(k)O(k)O(k),kkk为int型的32位,一次遍历空间复杂度:O(1)O(1)O(1),常数级变量,没有额外辅助空间方法二:位运算优化法(扩展思路)思路:有一个性质:n&(n−1)n\&(n-1)n&(n−1),会将n的二进制中最低位由1变成0我们可以不断让当前的 nnn与 n−1n - 1n−1做位与运算,直到 nnn的二进制全部变为 0 停止。因为每次运算会使得 nnn 的最低位的 1 被翻转成0,因此运算次数就等于 nnn 的二进制位中 1 的个数,由此统计1的个数。具体做法:step 1:使用循环检查nnn是否为0.step 2:不为0就与n−1n-1n−1做位与运算,去掉二进制最后一位的1,并统计次数。图示:Java实现代码:public class Solution { public int NumberOf1(int n) { int res = 0; //当n为0时停止比较 while(n != 0){ n &= n - 1; res++; } return res; }}C++实现代码:class Solution {public: int NumberOf1(int n) { int res = 0; //当n为0时停止比较 while(n){ n &= n - 1; res++; } return res; }};Python实现代码:class Solution: def NumberOf1(self , n: int) -> int: res = 0 #负数转换 if n < 0: n &= 0xffffffff #当n为0时停止比较 while n: n &= n - 1 res += 1 return res复杂度分析:时间复杂度:O(log2n)O(log_2n)O(log2n),nnn为数字的大小,循环次数等于nnn的二进制位中1的个数,最坏情况下nnn的二进制位全部为1,也即开一个2的log运算空间复杂度:O(1)O(1)O(1),常数级变量,没有额外辅助空间
点赞 199
评论 18
全部评论
推荐
最新
楼层
秋招专场
校招火热招聘中
官网直投
相关推荐
已经不能更加糟糕了
05-31 19:26
已编辑
广州大学 计算机类
深圳用友
点击就送的offer。一个月以来面了八次,只有两个oc了。一个是某家的驻场开发,另外一个是用友。想着自己现在啥也不会,不可能有机会冲中大厂,冲小厂又几乎都学不到东西,所以就选家驻场开发实习的。这是我说服自己的理由,太想早点上岸,放开手脚做一些想做的事情了。希望发展是,我能够在平常的实习中摸很多的鱼。Sping AOP 和 IOC 的原理是什么?依赖注入有多少种注解MyBatis 的一级缓存和多级缓存线程池创建的几个参数,以及对应的含义。线程安全怎么定义synchorized 和 lock 的区别java 中 悲观锁 由 synchorized 定义,那么 java 中的乐观锁是怎么定义的呢?j...
查看11道真题和解析
点赞
评论
收藏
转发
s8x
05-29 10:36
已编辑
门头沟学院 计算机类
为什么美团都挂了的志愿,又复活了
rt,之前二面完进人才库了,现在这个志愿二又复活了,约了晚上一面
美团一面926人在聊
点赞
评论
收藏
转发
勇敢的小冤种只想搞钱
05-27 03:44
门头沟学院 计算机类
Java加学院本,什么天崩开局
感觉重开才是最佳途径,4月开始投到现在,断断续续的投了几百份,没有面试。是简历不行还是投的太少啊 #最后再改一次简历#
最后再改一次简历
点赞
评论
收藏
转发
在求佛的牛油很忙碌
05-10 20:26
南昌大学 计算机类
25届找中小厂日常实习java
球球各位佬们指点一下!在学校这么久发现都在虚度光阴,什么都没有学会,突然醒悟可是时间实在不多,只能先找有完整教学的项目看一下,最近试着投过几个岗位,可是都没有什么动静,感觉整个人生都非常焦虑😭😭还是想问一下各位大佬意见,不想再自我折磨了,最终目标想进国企,不知道路线应该怎么规划,求指导😣😣 #实习,投递多份简历没人回复怎么办# #我的实习求职记录# #来聊聊你目前的求职进展# #投递实习岗位前的准备#
实习,投递多份简历没人回复怎么办
我的实习求职记录
点赞
评论
收藏
转发
多拿点offer
05-27 23:10
影石Insta360_技术研发部_视觉算法工程师(准入职员工)
影石insta360内推
5月还有HC!营销急缺!不限学校,不限学历,抓紧投递!【影石Insta360】2024春招启动拉Work-Life Balance!最快一周拿offer!全景相机全球市场占有率NO.1,产品远销全球200+国家和地区,营收规模在五年内翻10倍。【职位类别】技术类:算法、音视频、嵌入式、高性能计算、前后端、3D图形渲染、光学、移动开发、项目管理、硬件研发、结构研发产品类:产品经理、用户运营、米哈游、产品运营职能类:财务、法务、知识产权、人力资源业务类:市场、销售、电商、采购、物流、PMC、业务支持艺术类:设计、视频制作【薪资待遇】:8-40K/月+多项福利可以投递3个岗位,3-4轮面试投递链接:...
投递影石Insta360等公司10个岗位 >
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
给你们预测一下今年的秋招!
3149
2
...
深圳蟑螂真的很可怕吗
3108
3
...
【🎁】25届硬件牛牛互助计划(1期)
2910
4
...
阿里体检完还没发正式offer
2713
5
...
二本开发转测试,面试成功
2590
6
...
毕业了!
2259
7
...
海康暑期实习
2173
8
...
记录一下当前的想法 权当碎碎念
2165
9
...
5.31拼多多服务端开发实习生一面(75min)
2070
10
...
保融科技java实习面试凉经
1756
正在热议
#
和牛牛一起刷题打卡
#
14344次浏览
1314人参与
#
简历中的项目经历要怎么写?
#
14470次浏览
195人参与
#
不去互联网可以去金融科技
#
5547次浏览
70人参与
#
牛客帮帮团来啦!有问必答
#
1097291次浏览
16356人参与
#
面试被问第一学历差时该怎么回答
#
18468次浏览
204人参与
#
通信硬件薪资爆料
#
257099次浏览
2413人参与
#
工作两年想退休了
#
19467次浏览
243人参与
#
简历中的项目经历要怎么写
#
483107次浏览
8807人参与
#
如何看待offer收割机的行为
#
247128次浏览
3464人参与
#
简历无回复,你会继续海投还是优化再投?
#
23577次浏览
331人参与
#
实习生应该准时下班吗
#
93726次浏览
710人参与
#
你收到了团子的OC了吗
#
531431次浏览
6304人参与
#
参加过提前批的机械人,你们还参加秋招么
#
14128次浏览
343人参与
#
你的秋招进行到哪一步了
#
397313次浏览
6688人参与
#
晒一晒我的offer
#
3776386次浏览
58119人参与
#
你已经投递多少份简历了
#
339133次浏览
4907人参与
#
提前批和秋招有什么区别
#
29423次浏览
706人参与
#
实习与准备秋招该如何平衡
#
197838次浏览
3503人参与
#
你怎么评价今年的春招?
#
12605次浏览
194人参与
#
你的秋招进展怎么样了
#
558551次浏览
13953人参与
#
现在还是0offer,延毕还是备考
#
409735次浏览
4864人参与
牛客网
牛客企业服务