How to reduce time complexity for large data set inputs in this program?

Question

I have written this code to calculate the number of set bits between the range of numbers. My program gets compiled fine and giving proper output. It is taking too much time for large inputs and "Time limit exceeding".

#define forn(i, n) for(long int i = 0; i < (long int)(n); i++)
#define ford(i, n) for(long int i = (long int)(n) - 1; i >= 0; i--)
#define fore(i, a, n) for(long int i = (int)(a); i < (long int)(n); i++)


long int solve(long int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
    freopen("C:/Projects/CodeChef/SetBits/input.txt", "rt", stdin);
    freopen("C:/Projects/CodeChef/SetBits/output.txt", "wt", stdout);

    int tt;
    long long int num1;
    long long int num2;
    scanf("%d", &tt);
    forn(ii, tt) {
        unsigned long int bits = 0;
        unsigned long long int total_bits = 0;
        scanf("%lld",&num1);
        scanf("%lld",&num2);
        fore(jj, num1, num2+1) {
                bits = solve(jj);
                total_bits += bits;
                }

        printf("%lld\n",total_bits);
    }

    return 0;
}

Example test case:-

Sample Input: 3

-2 0

-3 4

-1 4

Sample Output:

63

99

37

For the first case, -2 contains 31 1's followed by a 0, -1 contains 32 1's and 0 contains 0 1's. Thus the total is 63.

For the second case, the answer is 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

Test case having large values:-

10

-1548535525 662630637

-1677484556 -399596060

-2111785037 1953091095

643110128 1917824721

-1807916951 491608908

-1536297104 1976838237

-1891897587 -736733635

-2088577104 353890389

-2081420990 819160807

-1585188028 2053582020

Any suggestions on how to optimize the code so that it will take less time. All helpful suggestions and answers will be appreciated with vote up. :)

Answer 1

I don't really have a clue what you are doing, but I do know you can clean up your code considerable, and you can inline you function.

Also I have taken the liberty of 'rephrasing' you code, you are using C++ like C and those defines are just grim and mapping the files onto stdio is even worse. I haven't tested or compiled the code but it is all there.

#include <fstream>

inline long int solve(long int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
    long first, last;
    unsigned count;
    std::ifstream inf("C:/Projects/CodeChef/SetBits/input.txt");
    std::ofstream off("C:/Projects/CodeChef/SetBits/output.txt");
    inf >> count;
    for(unsigned i=0u; i!=count; ++i) {
        inf >> first >> last;
        long total=0;
        ++last;
        for(long t=first; t!=last; ++t) {
            total+=solve(t);
        }
        off << total << '\n';
    }
    return 0;
}

A few ideas as to how you could be speed this up:

• you could build a std::map of the computed values and if they have been previously processed then use them rather than recomputing.
• do the same but store ranges rather than single values but that will be tricky. you could see if a value exists in the map and increment through the map until there are no more preprocessed values in which case start processing them for the iteration.
• check if there is a trivial sequence between on number and the next may be you could work out the first value then just increment it.
• may there is a O(1) algorithm for such a sequence
• Look at intel TBB and using something like tbb::parallel for to distribute the work over each core, because you are dealing with such a small about or memory then you should get a really good return with a large chunk size.