BINARY - Số nhị phân có nghĩa

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
using namespace std;

int n,k,c[40][40],a[40];

void init() {
    FOR(i,0,33) {
        c[i][0]=1;
        FOR(j,1,i)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
}

int get(int pos,int s0) {
    if (pos==0) {
        if (s0==0) return 1;
        else return 0;
    }
    int res=0;
    if (a[pos]) {
        //0
        if (pos<a[0] && s0>0) res=c[pos-1][s0-1];
        //1
        res+=get(pos-1,s0);
    }
    else {
        //0
        if (s0>0) res=get(pos-1,s0-1);
    }
    return res;
}

void solve() {
    a[0]=0;
    int saven=n;
    while (n) {
        a[++a[0]]=n&1;
        n>>=1;
    }
    n=saven;
    
    if (k>a[0]) {
        printf("0\n");
        return ;
    }
    
    int res=get(a[0],k);
    FOR(l,1,a[0]-1)
        res+=c[l-1][k];
    if (k==1) res++;
    printf("%d\n",res);
}

int main() {
    init();
    while (scanf("%d %d",&n,&k)==2) {
        if (n==0) {
            if (k==1) printf("1\n");
            else printf("0\n");
        }
        else solve();
    }
    return 0;
}

Download