Count total set bits in first N Natural Numbers

Given a positive integer n, determine the total number of set bits (1s) in the binary representation of all numbers from 1 to n, inclusive.

Examples:

Input: n = 3
Output: 4
Explanation: Numbers from 1 to 3: {1, 2, 3}
Binary Representation of 1: 01 -> Set bits = 1
Binary Representation of 2: 10 -> Set bits = 1
Binary Representation of 3: 11 -> Set bits = 2
Total set bits from 1 till 3 = 1 + 1 + 2 = 4
Input: n = 11
Output: 20

Try it on GfG Practice

Table of Content

[Naive Approach] Counting Bits for each number
[Expected Approach] Using Pattern Based Approach - O(logn) Time and O(logn) Space

[Naive Approach] Counting Bits for each number

The idea is simple, we loop from 1 to n, count the set bits (1s) in binary form of each number and keep adding them to a running total. After processing all numbers, the total represents the number of set bits from 1 to n.

C++

//Driver Code Starts
#include <iostream>
using namespace std;
//Driver Code Ends


// Function to get no of set bits in binary
// representation of positive integer n
int setBits(int n) {
	int count = 0;
	while (n) {
		count += n & 1;
		n >>= 1;
	}
	return count;
}

// Count total set bits in all 
// numbers from 1 to n
int countSetBits(int n)  {
   int res = 0;
   for (int i=1; i<=n; i++)
      res += setBits(i);
   return res;
}


//Driver Code Starts
int main() {
	int n = 11;
	cout << countSetBits(n);
	return 0;
}


//Driver Code Ends

Java

//Driver Code Starts
import java.util.Arrays;

class GfG {
//Driver Code Ends


    // Function to get no of set bits in binary
    // representation of positive integer n
    static int setBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

    // Count total set bits in all 
    // numbers from 1 to n
    static int countSetBits(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++)
            res += setBits(i);
        return res;
    }

//Driver Code Starts

    public static void main(String[] args) {
        int n = 11;
        System.out.println(countSetBits(n));
    }
}

//Driver Code Ends

Python

# Function to get no of set bits in binary
# representation of positive integer n
def setBits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Count total set bits in all 
# numbers from 1 to n
def countSetBits(n):
    res = 0
    for i in range(1, n + 1):
        res += setBits(i)
    return res


#Driver Code Starts
if __name__ == "__main__":
    n = 11
    print(countSetBits(n))

#Driver Code Ends

//Driver Code Starts
using System;

class GfG {
//Driver Code Ends


    // Function to get no of set bits in binary
    // representation of positive integer n
    static int setBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

    // Count total set bits in all 
    // numbers from 1 to n
    static int countSetBits(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++)
            res += setBits(i);
        return res;
    }

//Driver Code Starts

    static void Main(string[] args) {
        int n = 11;
        Console.WriteLine(countSetBits(n));
    }
}

//Driver Code Ends

JavaScript

// Function to get no of set bits in binary
// representation of positive integer n
function setBits(n) {
    let count = 0;
    while (n !== 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// Count total set bits in all 
// numbers from 1 to n
function countSetBits(n) {
    let res = 0;
    for (let i = 1; i <= n; i++)
        res += setBits(i);
    return res;
}


//Driver Code Starts
//Driver code
let n = 11;
console.log(countSetBits(n));

//Driver Code Ends

Output

Time Complexity: O(k*n), where k is the number of binary digits.
Auxiliary Space: O(1).

[Expected Approach] Using Pattern Based Approach - O(logn) Time and O(logn) Space

Instead of checking every number individually, we count how many times each bit position contributes as 1 in the entire range.

Since we know that for each bit in a binary number it follows a fixed periodic pattern as values increase. For the i-th bit (0-indexed), the pattern repeats for every period = 2⁽ⁱ⁺¹⁾
Within each period:

The bit remains 0 (unset) for the first half of the period.
The bit remains 1 (set) for the second half of the period.

So the total times ith bit set is: 2ⁱ.
If we take a example of n = 11, Let’s observe binary numbers from 0 to 7

Whenever the i-th bit becomes set for the first time (that happens at the number 2ⁱ), all the numbers before it (from 0 to 2^{(i − 1)}) follow a fixed pattern: in each bit position, half of the numbers have that bit set and half of the numbers have that bit unset. So in this pattern of 2ⁱ numbers, each bit becomes set 2ⁱ/ 2 = 2⁽ⁱ⁻¹⁾times.
And since there are i bit positions (from bit 0 to bit i−1), we multiply by i. So the total number of set bits becomes:

Total set bits = 2 ^i-1* i

After calculating the set bits in the full pattern from 0 to (2ⁱ− 1), we still have more numbers. The moment we cross 2^{i − 1} and reach 2ⁱ, the i-th bit becomes set. And from 2ⁱ up to the number where that i-th bit remains set (say N). So the i-th bit contributes (N − 2ⁱ + 1) set bits in this remaining part.
After solving the problem for the i-th set bit as the MSB, we then recursively solve the remaining part of the number and count the contribution of the next set bit.
For example:

C++

//Driver Code Starts
#include <iostream>
#include <cmath>
using namespace std;

//Driver Code Ends

int countSetBits(int n) {

    // Base case
    if (n == 0)
        return 0;

    // Find highest power of 2 less than or equal to n
    int x = log2(n);

    //Set bits in the full pattern 0 to (2^x - 1)
    int fullBits = x * (1 << (x - 1));

    //Contribution of the highest bit from 2^x to n
    int msbBits = n - (1 << x) + 1;

    //Recursively count remaining set bits after removing highest bit
    int remaining = n - (1 << x);
    int remainingBits = countSetBits(remaining);

    // Total set bits
    return fullBits + msbBits + remainingBits;
}

//Driver Code Starts

int main() {
    int n = 11;  
    cout << countSetBits(n);
    return 0;
}

//Driver Code Ends