对于1~n中在二进制表示下共有多少个1，如7就是12个1

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 31; //2^31大于1e9，枚举位数

typedef long long LL;

//f[]表示共有i位，所有位置都可以任意取0或1的 所有方案的 1的总数（即1~i中1的总数）
LL f[N];
int a[N], cnt;

//求组合数
int calc(int a, int b)
{
    int res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++ )
        res = res * i / j;
    return res;
}

//初始化所有1~i位共有几个1
void init()
{
    for(int i = 1; i < N; i ++ )
    {   
        //考虑1~i位中，第i位为1, 1~i-1中0的个数，即有i个位置，有k个0，有几种放法
        for(int k = 0; k <= i - 1; k ++ ) 
        //任意一种0的放法都对应一种方案，1的个数为i-k 乘以 方案, i-k为一个方案中1的个数
            f[i] += calc(i - 1, k) * (i - k);  

        //考虑第1~i位中，第i位为0，那么方案就由1~i-1中，第i-1位为1的方案转移而来
        f[i] += f[i - 1];
    }
}

LL dp(int n)
{
    cnt = 0;
    while(n) a[ ++ cnt] = n % 2, n /= 2;

    LL res = 0, last = 0;//res记录答案，last表示对于第i位之前出现过多少个1
    for(int i = cnt; i; i -- )
    {
        if(!a[i]) continue;//如果这一位是0,说明已经是最小了，这一位只能是0，跳过

    //否则这一位是1，可以枚举这一位是0的状态
    //那么第i位是0的时候由第i-1 ~ 1位的f数组来得出有多少1
    //对于第i+1~cnt的1由last记录,第1~i-1每一位有选和不选两种状态（考虑第i为0,last记录的1对结果的影响）
    //所以第i+1~cnt的1就是last * 2 ^ (i - 1),
        res += f[i - 1] + last * (pow(2, i - 1));
        last ++ ;
    }

    return res + last;
}

//暴力验证1~n中有几个1
int dfs(int x)
{
    if(!x) return 0;

    int res = 0;
    res += dfs(x - 1);

    while(x) res += x % 2, x /= 2;

    return res;
}

int main()
{   
    init();

    int n;
    while(cin >> n) cout << dp(n) << endl;

    return 0;
}

蓝桥2021国赛题目：他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 110;

LL n, k;
int b[N], cnt;

LL calc(int a, int b)
{
    //如果出现C00是合法的,返回res=1, C01是不合法的，因为第0位不能放1,返回0
    if(!a && b) return 0; //[①]这里直接特判掉也行，下面可以注释

    LL res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++ )
      res = res * i / j;

    return res;
}

LL dp(LL x)
{
    while(x) b[ ++ cnt] = x % 2, x >>= 1;

    LL res = 0;
    int last = 0;
    for(int i = cnt; i; i -- )
    {
        if(!b[i]) continue;

        //考虑第i位是0，其他1~i-1位随意放k-last个1的方案
        res += calc(i - 1, k - last);
        //出现C00的合法情况,如7,2   6=(110)很明显也是满足要求，但是由于最后一位是0
        //出现在第0位上方0个1，按照定义也是符合要求
        //对于7,15等全是1的数据都会少1（如果不特判）
        // if(i == 1 && last == k) res ++ ; [①]

        last ++ ;
        if(last > k) break; //如果出现1超出要求，即后面不可能再有合法方案，直接退出
    }

    if(last == k) res ++ ; //自己本身是否合法

    return res;
}

int main()
{
    cin >> n >> k;

    cout << dp(n) << endl;

    return 0;
}