Stuff...

test.cpp

#include <cstdio>
#include <cstdlib>
#include <assert.h>

/*** Factorial ***************************************************************/

#define FACT_LIMIT 17

bool fact_initialized = false;
unsigned long long G_FACTORIAL[FACT_LIMIT];

void init_fact() {
    if (!fact_initialized) {
        G_FACTORIAL[0] = 1;
        G_FACTORIAL[1] = 1;
        for (int i = 2; i < FACT_LIMIT; ++i)
            G_FACTORIAL[i] = G_FACTORIAL[i-1] * i;
        fact_initialized = true;
    }
}

unsigned long long fact(int n) {
    init_fact();
    return G_FACTORIAL[n];
}


/*** Permutations ************************************************************/

unsigned long long permutations32(int n, int r) {
    unsigned int numerator_prod = 1;
    int greater_denom = (r >= (n >> 1)) ? r : n - r;
    int lesser_denom = n - greater_denom;

    if (n == r || r == 0)
        return 1;

    for (int i = n; i > greater_denom; --i)
        numerator_prod *= i;

    return numerator_prod / fact(lesser_denom);
}


/*** Other Stuff *************************************************************/

// get i-th bit (from LSB) in n
inline unsigned int bitAt(int n, int i) {
    return (n >> (i-1)) & 1;
}

unsigned long long countOnesFromZero(int target, int bit, int offset) {
    if (bit == 0) return offset;

    if (bitAt(target, bit)) {
        unsigned long long sum = 0;
        for (int i = 0; i < bit; ++i) {
            sum += (i + offset) * permutations32(bit-1, i);
        }

        return sum + countOnesFromZero(target, bit-1, offset+1); 
    } else {
        return countOnesFromZero(target, bit-1, offset);
    }
}

long long countOnes(int left, int right) {
    unsigned long long count = countOnesFromZero(right, 32, 0);
    return count - countOnesFromZero(left - 1, 32, 0);
}

int main(int argc, char** argv) {
    int left = atoi(argv[1]);
    int right = atoi(argv[2]);

    init_fact();

    printf("L:%d <> R:%d\n", left, right);
    printf("RESULT: %ld\n\n", countOnes(left, right));
    return 0;
}