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:

WordPress.com Logo

You are commenting using your WordPress.com 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