# Counting Set Bits using Brian Kernighan’s Algorithm

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: 10Output: 2Binary representation of 10 is 1010 -> it has 2 set bitsInput: 32Output: 1Binary 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))` !

--

--

Software engineer in Singapore. Write random tech stuff. Still figuring out this “life” thing in life.