编程之美求二进制数中1的个数

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

题目：

对于一个字节（8bit）的变量，求其二进制中“1”的个数，要求算法的执行效率尽可能地高。

举例：

十进制整数162的二进制表示为10 100 010，则162的二进制数中1的个数为3.

要统计二进制数中1的个数，最容易想到的思路是从最右边开始逐个的看该位是否为1，如图1-1所示：

图1- 1 162的二进制表示

思路很简单，接下来就是分析该思路中涉及到的主要的技术点。

(1)如何判断该二进制位是否为1？

最简单的方式就是将该数与0x01做与操作即162& 0x01 = 0x0，如图1-2所示。

图1- 2 162&0x01

注：0x01为十六进制表示。

(2)如何从右开始逐个判断？

按照之前的思路，如图1-3我们希望箭头不停的往左移，通过移动箭头得到每一个二进制位。

图1- 3 箭头左移得到每一个二进制位

我们是否可以换个思路呢？箭头不动，而是让整数向右移呢？这种方式我们同样可以得到每一个二进制位。

图1- 4 箭头不动，二进制数向右移

很明显，我们希望整数右移，而箭头不变，因为这种方式编程非常的容易实现。整数右移一位，即162>> 1。

有了上述两个技术点的分析，接下来就可以利用C语言完成。

// 求二进制数中1的个数
int count(int v){
  int num = 0;//保存二进制数中1的个数
  while(v){
    num+=  v  & 0x01;//将二进制数与0x01做与操作
    v>> 1;// 二进制数右移一位
  }        
  return num;
}

您是否还有更好的解法呢？欢迎留言。

where2go 团队

微信号：算法与编程之美

温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！