首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

计算一个整数中含一的比特数

2012-08-01 
计算一个整数中含1的比特数注:代码引用自李亚锋的 《C面试真题精讲》解析部分为原创。原书中的解析有点不够清

计算一个整数中含1的比特数

注:代码引用自李亚锋的 《C面试真题精讲》

        解析部分为原创。原书中的解析有点不够清晰。

描述:

编写一个函数,实现功能为:输入一个无符号整数,计算出该整数中含1的比特个数。

如给定一个整数8(二进制为1000),它含1的比特数为1。


该题目的实现方法可以说是多种多样,如果不考虑效率的话,最简单的方法就是把该整数

先转换为2进制,对其每一位进行判断是否为1,然后统计总的含1的个数。

下面为代码:


这种方式很巧妙的。

解析如下:

n的二进制为32位。

最右侧为1的位可能为右查第1位,或者为右查第i(1<i<=32)位。

当为右查第一位时:

n-1的二进制为,最右侧一位为0.其他31位不变。

n和n-1相与得出的结果是,最右侧一位被置0的值。


当最右侧为1的位为第i(1<i<=32)位时,即右侧的第1到i-1位都为0.

这时,n-1的操作会将第i位置0,右侧的第1到i-1位置1。而第i+1为到32位都保持不变。

而相&之后会使0位至第i位都置0。

直到n=0时,就可以计算出bit位为1的个数。



热点排行