Count ones in binary representation

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

Author: Saurabh Purnaye

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s