算法-求二进制数中1的个数
任意给定一个32位无符号整数n,求n的二进制表示中1的个数,比如n = 5(0101)时,返回2,n = 15(1111)时,返回4
int BitCount2(unsigned int n)
{
unsigned int c =0 ;
for (c =0; n; ++c)
{
n &= (n -1) ; // 清除最低位的1
}
return c ;
}
为什么n &= (n – 1)能清除最右边的1呢?因为从二进制的角度讲,n相当于在n - 1的最低位加上1。
举个例子,8(1000)= 7(0111)+ 1(0001),所以8 & 7 = (1000)&(0111)= 0(0000),清除了8最右边的1(其实就是最高位的1,因为8的二进制中只有一个1)。再比如7(0111)= 6(0110)+ 1(0001),所以7 & 6 = (0111)&(0110)= 6(0110),清除了7的二进制表示中最右边的1(也就是最低位的1)。
参考:
https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 using1174@foxmail.com
文章标题: 算法-求二进制数中1的个数
文章字数: 204
本文作者: Jun
发布时间: 2018-10-26, 15:40:00
最后更新: 2021-06-27, 21:01:52
原始链接: http://yoursite.com/2018/10/26/算法-求二进制数中1的个数/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。