Solution review

We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this in a more efficient way using Briann’s Algorithm.

Brian Kernighan’s algorithm

This is a faster execution than the previous naive approach.

In this approach, we count only the set bits. So,

  • If a number has 2 set bits, then the while loop runs two times.

  • If a number has 4 set bits, then the while loop runs four times.

For example, let us consider the example n = 125 and calculate using this algorithm.

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy