Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java

How to count set bits in first k natural numbers

Ravi

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);
    }
}
Count set bits in first k natural numbers in Java

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.

RELATED TAGS

java
RELATED COURSES

View all Courses

Keep Exploring