需要跟题目中的描述反过来思考，优先考虑能走的最大值

#include <iostream>
using namespace std;

int step[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288};

int main()
{
    int target;
    cin >> target;
    int i, stepIndex = 0;
    int pos = 1, ans = 0;

    for (i = 19; i > 0; i--)
    {
        if (target - 1 >= step[i])
        {
            stepIndex = i;
            break;
        }
    }

    while (pos < target)
    {
        while (step[stepIndex] > target - pos && stepIndex >= 0)
        {
            stepIndex--;
        }
        pos += step[stepIndex];
        ans++;
    }

    cout << ans;
    return 0;
}

#include<stdio.h>

int main(){
	int n;
	scanf("%d",&n);
	
	long long tot[20];
	int i=0;
	int fig=1;
	for(i=0;i<20;i++){
		tot[i]=fig;
		fig*=2;
	}
	int count=0;
	n=n-1;
	
	for(i=19;i>=0;i--){
		if(n-tot[i]>=0){
			n-=tot[i];
			count++;
		}
		if(n==0){
			break;
		}
	}
	printf("%d",count);
	
	return 0;
	
}

一道贪心？题目 注意到2的19次方就已经大于n的最大取值，所以生成一个a[20]的数组即可。

#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
#include<math.h>

int main(){
	int i,n;scanf("%d",&n);
	int dis=n-1;
	int a[20];
	int c=1;
	int count=0;
	for(i=0;i<21;i++){
		a[i]=c;
		c*=2;
	}
	while(dis!=0){
	
	for(i=19;i>=0;i--){
		if(dis>=a[i]){
			dis-=a[i];
			count++;
			break;
		}
	}
	}	
	printf("%d",count);
    return 0;
}