编程之美求二进制数中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;

}

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