Related Tags

java

# How to count set bits in first k natural numbers

Ravi

### Problem statement

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

### 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

CONTRIBUTOR

Ravi
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time