365. 二进制中有多少个1
365. 二进制中有多少个1
和蔼的zhxing
发布于 2018-09-04 13:18:50
发布于 2018-09-04 13:18:50
计算在一个 32 位的整数的二进制表示中有多少个1.
比如：给定5，返回2。
思路一：遍历每一位，如果是1，计数器加1即可，也是最容易想到的，需要遍历一次，可以用不断除2来做，也可以用位操作，后者更简单些：
int countOnes(int num) {
int res=0;
for(int i=0;i<32;i++) //移位逐步操作
{
if((num>>i)&1)
{
res++;
}
}
return res;
// write your code here
}思路二：这也是题目中要求尽量每次只要把1找出来就行了，不要遍历那么多。 这个主要是要找到一个规律，规律就是n&(n-1)就能减少n的一个1，比7&6=（0111）&（0110）=（0110），9&8=(1001)&(1000)=(1000) ,从二进制的角度来看的话，n相当于在n-1的最低位加上1，所以取位与的话就可以达到这个效果，code：
int countOnes(int num) {
int res=0;
while(num!=0)
{
num&=num-1;
res++;
}
return res;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.11.15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读