How to count set bits in first k natural numbers

Problem statement

Given an integer kk, count the total number of set bits in binary representation of all numbers from 1 to kk.

Example

  • Input: k=5
  • Output: 7
k bin(k) Number of set bits
1 001 1
2 010 1
3 011 2
4 100 1
5 101 2

Total number of set bits is 7.

Solution

The solution is to loop through the numbers from 1 to k and for every number find the total number of set bits. Sum this count of number of set bits for all numbers.

Example

public class Main{
    public static int countSetBits(int number) {
        if (number == 0) {
            return number;
        }
        int setBitCounter = 0;
        while (number != 0) {
            number = number & (number - 1);
            setBitCounter++;
        }
        return setBitCounter;
    }
    public static void main(String[] args) {
        int k=5;
        int total = 0;
        for(int i=1;i <= k; i++)
            total += countSetBits(i);
        System.out.println("The total number of set bits in numbers from 1 to " + k + " is " + total);
    }
}

Explanation

  • Lines 3–14: The countSetBits() method is defined that takes a number and returns the number of set bits by unsetting the rightmost set bit until the number is 0.
  • Line 17: We define k.
  • Line 18: We define total that keeps track of the total number of set bits.
  • Lines 19–20: We run a loop from 1 to n where we find the number of set bits for each number by invoking countSetBits() method.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)