The task is to find ones in the binary representation of a number in given range. For an example: 1 is represented a 1 in binary so the number is 1’s in 1 is 1. Another example: 4 is represented as 100 in binary so number of 1’s in binary representation of 4 is 1.
In order to find 1’s in a very large range between 1 and 10,000,000 sounds complicated but can solved with following algorithm
#include <iostream>
#include <algorithm>
#include <cmath>
long long ccb(int col, int n) {
double division = (n + 1) / double(2 << col);
int sum = static_cast<int>(division);
long long rest = std::max(0.0, (division - sum) * (2 << col) - (1 << col));
return sum * (1 << col) + rest;
}
long long cab(int n) {
long long bits = 0;
for (int i = 0; i < 30; i++) {
bits += ccb(i, n);
}
return bits;
}
long long countOnes(int left, int right) {
return cab(right) - cab(left - 1);
}
