Changing Decimal to Binary and Counting the ones in it with really really Large numbers

Question

need to change decimals to binary from A to B and counting the ones in each number i turn into binary did all these except the time taken to do this of large numbers takes forever :D Here's my code:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string IntToBinary(long long number){
    string empty = "";
    while (number >= 1)
        if (number % 2 == 0){
            empty += '0';
            number /= 2;
        }
        else{
            empty += '1';
            number--;
            number /= 2;
        }
        reverse(empty.begin(), empty.end());
        return empty;
}

int main(){
long long A, B, count = 0;
while (cin >> A >> B){
    string temp;
    for (int i = A; i <= B; i++){
        temp = IntToBinary(i);
        for (int j = 0; j < temp.length(); j++){
            if (temp[j] == '1')
                count++;
        }
    }
    cout << count << endl;
    count = 0;
}
cin.get();
getchar();
return 0;
}

when i try to enter a large two numbers like 1000000000000000 10000000000000000 or 9007199254740992 9007199254740992 it takes forever =D

How do you expect the `int` of `i` to hold the `long long` values of `A` and `B`? If `B` is larger than the maximum size of `int` it will take *literally forever*. — Mark Ransom, Oct 27 '15 at 03:48

score 0 · Answer 1 · answered Oct 27 '15 at 04:04

while (number >= 1)
    if (number % 2 == 0){
        empty += '0';
        number /= 2;
    }
    else{
        empty += '1';
        number--;
        number /= 2;
    }

You can write that much more simply, without the if/else, as follows:

while (number >= 1)
{
    empty += (number % 2)+'0';
    number /= 2;
}

and you should count the 1's during this loop, not in a second loop.

Changing Decimal to Binary and Counting the ones in it with really really Large numbers

1 Answers1