How to count set bits in first k natural numbers
Problem statement
Given an integer , count the total number of set bits in binary representation of all numbers from 1 to .
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 is0. - Line 17: We define
k. - Line 18: We define
totalthat keeps track of the total number of set bits. - Lines 19–20: We run a loop from
1tonwhere we find the number of set bits for each number by invokingcountSetBits()method.
TRENDING TOPICS
