Count total set bits in all numbers from 1 to N

Vikram Shishupalsingh Bais -

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have presented an efficient approach to find the total number of set bits in all numbers from 1 to N in O(logN) time by deriving a pattern and a formula.

Table of contents:

  1. Problem Statement
  2. Brute Force Approach
  3. Efficient Mathematical Approach

Let us get started with Count total set bits in all numbers from 1 to N.

Problem Statement

Given a positive integer N, our task is to count the total number of set bits in the binary representation of all the numbers from 1 to N.

Example

Let input N = 5

then we have to count total set bits in digit 1 to 5

  • for (1)10 => (0001)2, set bits = 1
  • for (2)10 => (0010)2, set bits = 1
  • for (3)10 => (0011)2, set bits = 2
  • for (4)10 => (0100)2, set bits = 1
  • for (5)10 => (0101)2, set bits = 2

Total set bits = 7

Therefore, for N = 5, result is 7.

Brute Force Approach

In this approach we will create a loop and we will traverse that loop from 1 to N.

For each digit from 1 to N, we will check how many set bits they have and sum up those number of set bits to get answer.

Pseudocode

  1. Take input as N
  2. Create "counter" and initialize it to 0
  3. For each digit in range 1 to N check total number of set bit
  4. Increment the "counter" with total set bits we got
  5. We will get our result in "counter"

Code

Following is the implementation of our Brute Force approach:

#include<bits/stdc++.h>
using namespace std;

int count_bits(int n){
  int c=0;
  while(n>=1){
    if((n&1)==1) c++;
    n>>=1;
  }
  return c;
}

void solve()
{
  int n; cin>>n;
  int counter=0;
  for(int i=1; i<=n; i++){
    counter += count_bits(i);
  }
  cout<<counter<<endl;
}

int main() {
  solve();
  return 0;
}

Input

11

Output

20

Explanation

Let n be 5

then initialize counter=0

in each iteration from 1 to 5 we will get following result

  • for (1)10 => (0001)2, set bits = 1, counter += 1
  • for (2)10 => (0010)2, set bits = 1, counter += 1
  • for (3)10 => (0011)2, set bits = 2, counter += 2
  • for (4)10 => (0100)2, set bits = 1, counter += 1
  • for (5)10 => (0101)2, set bits = 2, counter += 2

We will get counter=7 that will be our result

Time Complexity

The Time Complexity of our Brute Force approach is: O(N logN)

We are traversing from loop N times and each time we are traversing bits which will take logN time as a number N has O(logN) bits.

Space complexity

The Space Complexity of our Brute Force approach is: O(1)

Efficient Mathematical Approach

In this approach, we will observe the occurrence of set bits in each index of number

Example

let N be 14

then,

  • (0)10 => (0000)2
  • (1)10 => (0001)2
  • (2)10 => (0010)2
  • (1)10 => (0011)2
  • (4)10 => (0100)2
  • (5)10 => (0101)2
  • (6)10 => (0110)2
  • (7)10 => (0111)2
  • (8)10 => (1000)2
  • (9)10 => (1001)2
  • (10)10 => (1010)2
  • (11)10 => (1011)2
  • (12)10 => (1100)2
  • (13)10 => (1101)2
  • (14)10 => (1110)2

For perfect power of 2 (ex 2, 4, 8) we can say that number of set bit before number that is power of 2.

nbits = k*2(k-1) ,

where k = log2(n) [highest power of two less than given number]

Value of n = (14)10

Then largest power of 2 is 8

Therefore we can say that total number of set bits before 8 => 3*22 => 12 [k = log2(14) = 3.8 = 3 as we have to take floor of 3.8]

for remaining digits which are

  • (8)10 => (1000)2
  • (9)10 => (1001)2
  • (10)10 => (1010)2
  • (11)10 => (1011)2
  • (12)10 => (1100)2
  • (13)10 => (1101)2
  • (14)10 => (1110)2

Now we can see that 4th index of each number is common so we can remove 4th index by including count for that index

Total 4th index which is set is total number remaining therefore

Total highest index with set bits = (n-2k+1) = (n-23+1)
after counting highest set index we can now remove those index for understanding

Now after removing those index our remaining number became:

  • (000)2 => (0)2
  • (001)2 => (1)2
  • (010)2 => (2)2
  • (011)2 => (3)2
  • (100)2 => (4)2
  • (101)2 => (5)2
  • (110)2 => (6)2

Now we can see the sequence ranging from 0 to 6 with same pattern as before
with highest power of 2 as 4 now we can call function recursively to find total set bits for this new sequence

Therefore in our formula we will recursively call function [ func(n-2k] by sending value 6 for calculating total set bits

int func(int n){
  if(n<=1) 
      return n;
  // for finding highest power of 2 less 
  // than given number n
  int k = floor(log2(n));
  return (k) * pow(2, k-1) + 
         (n-pow(2, k)+1) + func(n-pow(2, k));
}
  • (k)*pow(2, k-1) => total set bits before highest power of 2 that is less than n
  • (n-pow(2, k)+1) => adding count of set bit at front bit in remaining numbers
  • func(n-pow(2, k)) => calling function recursively to perform same operation with new number got from remaining sequence

From this formula we get following expression as result

total set bits = (3 * 22) + (14 - 23+1) + (func(14-23))

total set bits = (12) + (7) + (9) = 28

Pseudocode

  • take input as n
  • get largest power of 2 where (2^k<n)
  • calculate total set bits before largest power + front index bits of remaining numbers greater than highest power of 2 + call function recursively to get total set bits in new number we get by removing front bit from old sequence

Code

#include<bits/stdc++.h>
using namespace std;
int count_bits(int n){
  if(n<=1) return n;
  int k=floor(log2(n));
  return (k)*pow(2, k-1)+(n-pow(2, k)+1)+count_bits(n-pow(2, k));
}

void solve()
{
  int n; cin>>n;
  cout<<count_bits(n)<<endl;
}

int main() {
  solve();
  return 0;
}

Input

11

Output

20

Time complexity

The Time Complexity of our efficient approach is: O(logN).

Space complexity

The Space Complexity of our efficient approach is: O(1)

With this article at OpenGenus, you must have the complete idea of Counting total set bits in all numbers from 1 to N.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.