【五一创作】AcWing——凑数（二进制中1的个数）

ゝ一纸荒年。 2023-09-27 18:05 72阅读 0赞

[4941. 凑数 - AcWing题库][4941. _ - AcWing]

## 1、题目 ##

初始时，n=0。

每一轮操作都要依次完成两个步骤：

*  第一步，任选一个**非负**整数 a，将 n增加 a，这一步所需付出的代价为 a。
 *  第二步，将 n 乘以 2，这一步无需付出任何代价。

你可以不断重复上述操作。

给定一个整数 x，你的任务是使 n 在某一步操作后（不一定是某一轮结束后）恰好等于 x 且付出的总代价尽可能少。

请你计算，为了完成任务所需付出的最小总代价。

例如，如果 x=5，则最佳操作方案为：

*  第 1 轮操作中，第一步，将 n 增加 1（付出代价 1），使得 n 变为 1，第二步，将 n 乘以 2，使得 n 变为 2。
 *  第 2 轮操作中，第一步，将 n 增加 0（付出代价 0），则 n 仍然为 2，第二步，将 n 乘以 2，使得 n 变为 4。
 *  第 3 轮操作中，第一步，将 n 增加 1（付出代价 1），使得 n 变为 5。此时 n 等于 x 成立，任务完成。
 *  付出的最小总代价为 2。

再例如，如果 x=8，则最佳操作方案为：

*  第 1 轮操作中，第一步，将 n 增加 1（付出代价 1），使得 n 变为 1，第二步，将 n 乘以 2，使得 n 变为 2。
 *  第 2 轮操作中，第一步，将 n 增加 0（付出代价 0），则 n 仍然为 2，第二步，将 n 乘以 2，使得 n 变为 4。
 *  第 3 轮操作中，第一步，将 n 增加 0（付出代价 0），则 n仍然为 4，第二步，将 n 乘以 2，使得 n 变为 8。此时 n等于 x 成立，任务完成。
 *  付出的最小总代价为 1。

**输入格式**

一个整数 x。

**输出格式**

一个整数，表示所需付出的最小总代价。

**数据范围**

前 3 个测试点满足 1≤x≤10。  
所有测试点满足 1≤x≤10⁹。

**输入样例1：**

**输出样例1：**

**输入样例2：**

**输出样例2：**

## 2、题目解读 ##

> 看完题目我们知道了加法需要付出代价，乘法不需要付出代价，也就是说我们应该尽量使用乘法去使n变成x。
> 
> 我们 n(0)->x 可能困难，可是 x->n(0) 就简单了，这时乘法就变成了除法（除以2），而思路就出来了我们应该 使用减法（最小代价就是减1）将x保持成偶数，再x除以二，不断重复上面过程就可以求解出答案。
> 
> 仔细推敲可以发现，就是求 n二进制中 1 的个数。那么这样我们也随便复习一下怎样求二进制中 1 的个数吧！

## 3、代码 ##

Ⅰ、正常求解

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
             Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int i=0;
            while (n!=0){
                if (n%2==0)
                    n/=2;
                else {
                    n-=1;
                    i++;
                }
            }
            System.out.println(i);
        }
    }

Ⅱ、使用Integer.bitCount()方法：这是一种内置于Java的方法，通过调用该方法即可计算一个整数中1的个数。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            System.out.println(Integer.bitCount(n));
        }
    }

Ⅲ、可以使用位运算符和循环来计算一个二进制数中1的个数。算法基本思路是将目标数每次右移一位，并且与1进行与运算，如果结果为1，则说明当前位是1，否则为0。循环直到目标数变为0。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
           Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int count = 0;
            while (n > 0) {
                if ((n & 1) == 1) {
                    count++;
                }
                n >>= 1;
            }
            System.out.println(count);
        }
    }

Ⅳ、Brian Kernighan算法：该算法是一种优化的常规方法，它的基本思路是利用n&(n-1)可以将n最右边的1变成0的特性，循环直到目标数变为0。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
           Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int count = 0;
            while (n > 0) {
                n &= (n - 1);
                count++;
            }
            System.out.println(count);
        }
    }

[4941. _ - AcWing]: https://www.acwing.com/problem/content/description/4944/