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 1s.
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 1s(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)) !
