Trusted answers to developer questions

Ravi

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

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

.

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.

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

- 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

Related Courses