[算法学习]计算出二进制数中1的个数

算法

问题描述： 计算出二进制数中1的个数。

解法一：循环计数

解法与分析： 使用一个数1来“与”二进制数中每一位，若值为1则1的个数加一。

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 通过flag左移做一个循环来与num的每一位，若与计算的结果不为0，则1的个数++
 * @param num
 * @return
 */
public static int calc2(int num)
{
    int count=0;
    int flag=1;
    while (flag!=0)
    {
        if((num&flag)!=0)
        {
            count++;
        }
        flag<<=1;
    }

    return count;
}

解法二：最佳算法

解法与分析： 设二进制数为num，若num不为0时，num-1后的值与num相与都会消除一个1，按照这一点，可以很快计算出1个个数。

参考代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * num不为0时，num-1后的值与num相与都会消除一个1，按照这一点，可以很快计算出1个个数，最佳算法
 * @param num
 * @return
 */
public static int calc3(int num)
{
    int count=0;
    while (num!=0)
    {
        num=num&(num-1);
        count++;
    }
    return count;
}