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); }