In short, Brian Kernighan’s Algorithm is used to count the number of `1`

(also known as *set bits*) in a binary number. The main concept here is when we subtract one from any number, all the bits after the least significant/rightmost *set bits *will be inverted!

Let’s look at a binary representation of 1 to 10.

Notice as we go down the list of number, the bits, including the rightmost `1`

are flipped, highlighted in orange.

Now, let’s imagine what will happen when you do a bitwise AND(`&)`

operator on a number(i.e. 10) and the number before it(i.e. 9)? What is a bitwise AND operator you say?

# Bitwise AND operator

Basically, the bitwise AND operator (`&`

) returns a `1`

in each bit position if the corresponding bits of both binary numbers are `1`

s.

Let’s take the number 10 and the number 9 in their binary forms as example

You can see that only the `1`

in 2³ column remains as both the number 10 and 9 have `1`

in their 2³.

How about the number 8 and 7?

All the `1`

are gone! The bits in both number have to be `1`

for AND operator to be `1`

.

Now that we understands the concept, we are ready to tackle the problem. You can use this decimal-to-binary converter to better visualise a number in its binary representation.

# Problem Statement: Count the number of bits

Write a program to count the number of `1`

s(*set bits*) in the binary representation of an integer.

Input: 10

Output: 2

Binary representation of 10 is 1010 -> it has 2 set bitsInput: 32

Output: 1

Binary representation of 32 is 100000 -> it has 1 set bit

# Solution: Brian Kernighan’s Algorithm

Let’s do a visual walkthrough using the number 10

On the first loop, we are doing a bitwise AND operator on 10 and 9, like so:

The result of `number & (number — 1)`

is 8 (2³ = 8). We assign this result to `number`

. We then increment `count`

by 1 (`count`

is now 1)

On the second loop, we are doing a bitwise AND operator on 8 and 7, like so:

The result of `number & (number — 1)`

is 0! We assign this result to `number`

. We then increment `count`

by 1 (`count`

is now 2).

Since now `number`

is 0, the loop will end, and `count = 2`

is returned.

If you do this exercise on the number 32(binary representation is `10000`

), the loop will end after 1 loop!

# Space and time complexity

The space complexity is `O(1)`

as the space used does not grow with the input.

The time complexity is `O(log(n))`

as the algorithm goes through as many iterations as there are set bits. An integer `n`

has `log(n)`

bits, so the worst case would be `O(log(n))`

!