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);}}

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

TRENDING TOPICS