# Kernighans Algorithm #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given a number n.2. You have to count the number of set bits in the given number.`
Input Format
`A number n`
Output Format
`Number of set bits in n`
Question Video
Constraints
`1 <= n <= 10^9`
Sample Input
`58`
Sample Output
`4`

• Editorial

The problem here deals with counting the number of set bits present in the given input number. For example, n = 58 => [ 1 1 1 0 1 0 ] then the output should be 4.

There can be many approaches to solve the problem, one of them can be to traverse over the entire 32 bits and count the number of set bits by making the mask for every bit and checking for is the bit set or not. This would have a time complexity of 32 * constant.

This can be further optimized by using Kernighans Algorithm which makes use of an RSB mask. So with every iteration, we calculate the RSB mask of the number and then subtract it from the number until the number becomes zero. In this way, we have a time complexity of k * constant where k is the number of set bits in n. Hence in this algorithm our code jumps over set bits from right to left to count the set bits.  Time Complexity: O(k)

The time complexity for the function is nearly constant proportional to the number of set bits.

Space Complexity: O(1)

The space complexity for the function is constant.

• Related Topics

Run

Run
Id Name