LeetCode如何输出某个整数二进制中1的个数
这篇文章将为大家详细讲解有关LeetCode如何输出某个整数二进制中1的个数,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
成都创新互联公司服务项目包括忻州网站建设、忻州网站制作、忻州网页制作以及忻州网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,忻州网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到忻州省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
题目描述
请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9转换为二进制是1001,有2位是1。因此如果输入9,该函数输出2.
示例1
输入:0x7FFFFFFF
输出:31
示例2
输入:4055
输出:10
题目解析
设置一个 flag ,初始时设置为 1 ,然后与输入的数 n 进行与 &
运算,结果不为零,则表明 n 当中与 flag 相同位置的二进制位为 1 ,count
加 1,每次 flag 左移一位,直到数 n 所对应的二进制的第一位,执行次数为数 n 转化为二进制之后的位数。
还有一种方法就是面试官喜欢的方式了,仅执行数 n 转化为二进制之后 1 个位数次。
比如 9 的二进制表示为:
我们将 9 减 1 ,对应的就是 9 的二进制中最右边的一个 1 变成了 0,其之后的位置全变为 1 .
然后我们将 8 和 9 进行位与运算,并将结果保存在 n = n & (n-1)=8
,然后对 n
继续重复上述步骤,直到 n = 0
为止。
8 减去 1 为 7:
然后让 8 和 7 进行与运算,结果为 0 ,总共执行 2 次,9 的二进制中 1 的个数为 2.
动画描述
代码实现
int NumberOf1_Solution1(int n)
{
int count = 0;
unsigned int flag = 1;
while (flag)
{
if (n & flag)
count++;
flag = flag << 1;
}
return count;
}
int NumberOf1_Solution2(int n)
{
int count = 0;
while (n)
{
++count;
n = (n - 1) & n;
}
return count;
}
时间复杂度
Solution1 的时间复杂度为数n
的二进制位数。
Solution2 的时间复杂度为数n
的二进制中 1 的个数。
关于“LeetCode如何输出某个整数二进制中1的个数”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。
网页题目:LeetCode如何输出某个整数二进制中1的个数
新闻来源:http://myzitong.com/article/jpejdg.html