首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
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 22:41
北京邮电大学 电子信息类
最离谱的面试,快手暑期实习经历分享
为了防止自己情绪化发言,我先如实叙述一下时间线。29日 约定30日晚8点线上面试30日 19:50 我进入面试间等待面试20:05 面试官未进入,我按照提示拨打HR电话,无法接通20:10 我给HR发送邮件,无回复20:13 我短信给HR同步情况,HR回复联系面试官20:15左右 面试官进入面试间,介绍部门及自己姓名,随后让我进行自我介绍20:20左右,我完成自我介绍,面试官没有回应,我尝试在面试间尝试使用语音和文字与面试官交流,面试官均无回应,同时我能清晰听到面试官工作软件的提示音和敲击键盘的声音,与画面完全同步。20:23 我向HR反应面试官不进行任何交流的情况,无回应,随后我多次在面试间...
投递快手等公司10个岗位 >
点赞
评论
收藏
转发
匿名牛油
不愿透露姓名的神秘牛友
05-28 14:34
大疆嵌入式面经一面(40min)
1、自我介绍2、项目介绍3、项目中遇到过哪些困难,怎么解决的4、linux知识点考察※5、对大疆的了解,公司,产品线等等6、反问
大疆一面6人在聊
查看4道真题和解析
点赞
评论
收藏
转发
qrna
04-15 11:06
腾讯_csig_机器学习算法研究(实习员工)
轮到我写感谢信了
经过多平台投票调研,以及和多位朋友深入讨论,最终决定放弃百度的offer,全身心拥抱鹅厂
点赞
评论
收藏
转发
杰米砖石段位玩家
05-28 16:04
腾讯云智研发_智子研发中心_客户端开发(实习员工)
第二天要求到岗
真的无语了
点赞
评论
收藏
转发
被升职的小饼干很高大
05-29 19:44
山东师范大学 计算机类
一个普通双非女生的秋招之路
大家好,我是小布丁。先简单地做个自我介绍:我今年本科毕业于某双非院校(属于那种没什么人听说过的小学校),学的是计算机专业,英语四级水平(没办法,六级确实没过)。我本科时期走的是后端这条路,主攻语言C++,系统学习过操作系统,计算机网络,MySql,Redis,算法也刷了600+,造化弄人,秋招后走向了客户端这条“不归路”。公司还够得上中厂,薪资也够我在一线苟活一直想写篇帖子来记录秋招经历,希望能帮到新手小伙伴们~实习Part 想了想还是把实习经历放这了,因为这段实习经历确实对我的秋招帮助很大。去年五月份我找到了人生第一份实习,是北京的一个小公司,说是后端吧其实也就写写脚本,打包打包软件,...
我的实习求职记录
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
给你们预测一下今年的秋招!
3044
2
...
深圳蟑螂真的很可怕吗
2362
3
...
【🎁】25届硬件牛牛互助计划(1期)
2279
4
...
记录一下当前的想法 权当碎碎念
2197
5
...
5.31拼多多服务端开发实习生一面(75min)
2155
6
...
二本开发转测试,面试成功
1959
7
...
阿里体检完还没发正式offer
1945
8
...
毕业了!
1685
9
...
momenta 实习 C++ 一面
1501
10
...
海康暑期实习
1479
正在热议
#
和牛牛一起刷题打卡
#
14444次浏览
1321人参与
#
简历中的项目经历要怎么写?
#
14539次浏览
196人参与
#
不去互联网可以去金融科技
#
5931次浏览
78人参与
#
牛客帮帮团来啦!有问必答
#
1098377次浏览
16365人参与
#
面试被问第一学历差时该怎么回答
#
18511次浏览
205人参与
#
通信硬件薪资爆料
#
257374次浏览
2414人参与
#
工作两年想退休了
#
19535次浏览
244人参与
#
简历中的项目经历要怎么写
#
483307次浏览
8812人参与
#
如何看待offer收割机的行为
#
247247次浏览
3464人参与
#
简历无回复,你会继续海投还是优化再投?
#
23596次浏览
331人参与
#
实习生应该准时下班吗
#
93868次浏览
710人参与
#
你收到了团子的OC了吗
#
531585次浏览
6307人参与
#
参加过提前批的机械人,你们还参加秋招么
#
14145次浏览
343人参与
#
你的秋招进行到哪一步了
#
397444次浏览
6691人参与
#
晒一晒我的offer
#
3777849次浏览
58134人参与
#
你已经投递多少份简历了
#
339282次浏览
4910人参与
#
提前批和秋招有什么区别
#
29442次浏览
708人参与
#
实习与准备秋招该如何平衡
#
197964次浏览
3504人参与
#
你怎么评价今年的春招?
#
12652次浏览
194人参与
#
你的秋招进展怎么样了
#
558776次浏览
13955人参与
#
现在还是0offer,延毕还是备考
#
409863次浏览
4865人参与
牛客网
牛客企业服务