首页 > 剑指offer:面试题15. 二进制中1的个数

剑指offer:面试题15. 二进制中1的个数

题目:二进制中1的个数

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

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

示例 2:

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

示例 3:

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

解题:

n - 1的二进制值一定会把原二进制值右起的第一个1变成0,而这个1右边的所有0都会变成1,再进行按位与运算的话,就会把n二进制中右起第一个1去掉,同时也会把n-1二进制刚刚增加的1也变成0,所以相对n来说,n&n-1就会少了右起第一个1。

所以如果我们如果进行如下运算:

while (n) { n = n & n - 1; }

每一次循环,都会消掉最右边的1,直到所有1都消去,所以只要再弄个变量计数,就能统计n二进制中1的个数。

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

 

更多相关:

  • CentOS7自带的git版本1.8.3.1,这个版本有点低了。于是决定折腾升级, 实操记录在此: 1、确认你的当前git版本 在终端输入: git --version   2、使用root账号 在终端终入: su root 然后输入root账号的密码,注意linux下输密码时界面是没有变化的   3、配置存储库 启用Wa...

  • 今天做TJU的OJ ,其中一道题是先读入一个字符串,再读入一个整数,循环往复,直到字符串是空,也就是说回车键结束循环。 但是cin对空格和回车都不敏感,都不影响继续读入数据,所以需要一种新的方式检测回车。 方法一:利用getchar()函数 1 //**************************将输入的单词逆序输出*****...

  • 题目描述: 根据输入的运算符对输入的整数进行简单的整数运算。 运算符只会是加+、减-、乘*、除/、求余%、阶乘!六个运算符之一。 输出运算的结果,如果出现除数为零,则输出“error”,如果求余运算的第二个运算数为0,也输出“error”。 输入: 输入为一行。先输入第一个整数,空格输入运算符,然后再空格输入第二个整数,回车结束...

  • 1、调出命令窗口:开始---->运行---->cmd,或者是window+R组合键   2、输入命令:netstat -ano,列出所有端口的情况。在列表中我们观察被占用的端口,比如是4300,我们拿它来做实验。 3、查看被占用端口对应的PID,输入命令:netstat -aon|findstr "4300",回车,记下最后一位...

  • 关于这个问题其实我很早之前就研究过,只是一直都是弄一次就不管了,下次就忘记怎么弄了,又去查,现在就写个笔记吧。 win8/8.1 在开始的界面输入netplwiz,或者点击win+r打开运行,输入netplwiz,然后回车 会弹出这个框框 然后会然你输入密码,输入之后点击确定就可以了。   winXP/7: 这个系统有点不同 使用...

  • 全卷积网络(FCN) 1.全卷积神经网络介绍 FCN对图像进行像素级的分类,从而解决了语义级别的图像分割(semantic segmentation)问题。与经典的CNN在卷积层之后使用全连接层得到固定长度的特征向量进行分类(全联接层+softmax输出)不同,FCN可以接受任意尺寸的输入图像,采用反卷积层对最后一个卷积层的fea...

  • printf()函数优点在于可以格式化输出 格式:   %['padding_character][-][width][.precision]type   所有的转换说明都是以%开始,如果想打印一个%符号,必须用%% ;   参数“'padding_character”是可选,它将被用来填充变量直至所指定的宽度,该参...

  • 给定一个长度不超过10000的、仅由英文字母构成的字符串。请将字符重新调整顺序,按GPLTGPLT....这样的顺序输出,并忽略其它字符。当然,四种字符(不区分大小写)的个数不一定是一样多的,若某种字符已经输出完,则余下的字符仍按GPLT的顺序打印,直到所有字符都被输出。 输入格式: 输入在一行中给出一个长度不超过10000的、仅...

  • 给定两个整数A和B,输出从A到B的所有整数以及这些数的和。 输入格式: 输入在一行中给出2个整数A和B,其中−100≤A≤B≤100,其间以空格分隔。 输出格式: 首先顺序输出从A到B的所有整数,每5个数字占一行,每个数字占5个字符宽度,向右对齐。最后在一行中按Sum = X的格式输出全部数字的和X。 输入样例:...

  • python面试题目 原文地址:https://www.usblog.cc/blog/post/justzhl/b5cc9a05c7d2 问题一:以下的代码的输出将是什么? 说出你的答案并解释。 ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Parent(object):     x...