当前位置：首页 > article >正文

算法41：位1的个数

article 2024/9/20 21:32:45

一、需求

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中
设置位的个数（也被称为汉明重量）。

示例 1:

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2:

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3:

输入：n = 2147483645
输出：30
解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。

提示:

1 <= n <= 2^31 - 1

进阶：

如果多次调用这个函数，你将如何优化你的算法？

二、思路分析图

（一）循环检查二进制位

在这里插入图片描述

三、代码

（一）数据初始化

/**
 * 入口
 * 191、位1的个数
 * 输入：
 * nums = 11（1101）
 * 输出：（1的个数）
 * result1 = 3
 * 解释：
 * 1.循环检查二进制位
 * 2.位运算优化
 * 3.循环检查二进制位调优
 */
@Test
public void suanfa43()
{
    // 初始化
    int num = 11;
    int index = getHammingWeight(num);
    System.out.println("循环检查二进制位 = " + index);
    int index1 = getHammingWeightOne(num);
    System.out.println("位运算优化 = " + index1);
    int index2 = getHammingWeightTow(num);
    System.out.println("循环检查二进制位调优 = " + index2);
}

（二）循环检查二进制位【自己写的方案】

/**
 * 循环检查二进制位
 *
 * @param n
 * @return
 */
private int getHammingWeight(int n)
{
    int index = 0;
    while (n != 0)
    {
        if (n % 2 == 1)
        {
            index++;
        }
        n /= 2;
    }
    return index;
}

（三）位运算优化

/**
 * 位运算优化
 *
 * @param n
 * @return
 */
private int getHammingWeightOne(int n)
{
    int ret = 0;
    while (n != 0) {
        n &= n - 1;
        ret++;
    }
    return ret;
}

（四）循环检查二进制位调优

/**
 * 循环检查二进制位调优
 *
 * @param n
 * @return
 */
private int getHammingWeightTow(int n)
{
    int index = 0;
    while (n != 0)
    {
        index += n % 2;
        n /= 2;
    }
    return index;
}