Counting Binary Number Islands

Counting islands of the binary representation of a number is a fun and somewhat challenging problem depending on the requirements of the solution.

We will use this simple problem to showcase exploiting the binary nature of numbers to speed up a calculation.

Problem

Say we are given a positive integer $n$, we want to find out how many islands of 1’s are in the binary representation of the given number.

For example, let’s take the number $1234$. Converting it to binary, we get $0100 1101 0010$. We count islands of 1’s by looking at how many sections continuously repeating 1’s we have.

We can see for our example we have a total of $4$ islands.

Constructing a Solution

Looking at the problem, we can take two approaches. We can try to solve the problem mathematically or programmatically.

In the mathematical approach we are asking ourselves: Is there a fundamental structure to the problem that we can exploit? Is there a pattern that numbers with certain amount of islands inhibit?

On the other hand, with a programmatic approach, we are trying to use simple operations over many steps to extract the number of islands.

Trivial Solution

A simple solution involves using a right logical shift operation while counting the number discontinuities encountered on the least significant bit.

1
def count_islands(x: int):
2
    count = 0
3
    seeing_ones = False
4
    while x != 0:
5
        is_last_digit_one = bool(x & 0b0001)
6
        if seeing_ones:
7
            if not is_last_digit_one:
8
                seeing_ones = False
9
        else:
10
            if is_last_digit_one:
11
                count = count + 1
12
                seeing_ones = True
13
        x = x >> 1
14
    return count

There are three important parts to this code. As you can see I have labeled them in reverse, because each subsequent part plays into the previous one.

The first is the logical shift operation. By performing a right logical shift we are moving all the bits to the right while also discarding the least significant bit. Because we are using a logical shift, the bit added to the right will always be a zero.

The second is detecting the one in the least significant bit. We do this by masking the current number with a number that only has the least significant bit active. So, in case the least significant bit is set, we get one as the output. While in case it is clear, we get a zero.

Finally, the third part serves two purposes, it detects if the provided numbers contains any islands and it insures we terminate the loop when there are no more ones to count.

Input Transformation

Obviously we can’t keep it at the trivial solution. Now, the interesting part is looking at how can we improve it.

Looking at the initial approach there doesn’t seem to be an obvious improvement. We want to count the number of islands and our solution goes through the numbers and counts them. It doesn’t perform any unnecessary operations. So what do we do?

Instead of trying to optimize the steps, we can transform the input to simplify the algorithm.

1
def count_islands(x: int):
2
    count = 0
3
    x = x & ~(x << 1)
4
    while x != 0:
5
        count = count + (x & 0b0001)
6
        x = x >> 1
7
    return count

The overall structure is very similar to the initial algorithm, but the loop code is significantly reduced. The most significant change comes before the loop where we are modifying the input before starting to loop. The transformation is a clever trick where we are replacing each island of 1’s with just a single 1. Then we can just count the number of 1’s thereby removing the additional logic for handling islands of multiple 1’s.

Let us take an example to showcase how this transformation works. Again we will use the number $1234$.

The transformation consists of three steps. The first step shifts the islands to the left. By their nature islands need to have zero(s) separating them, so shifting makes a single one take place of a zero for each island. Steps two and three exploit this fact by masking the shifted input with the initial input, thereby keeping only ones that took the place of a zero. This makes every island reduced to one member which we can then easily count, simplifying the iteration.

Fun fact! The implementation can be further improved by exploiting the POPCOUNT instruction. In Python we can’t access such instruction, but using int.bit_count we can get pretty close. This is because under the hood it uses POPCOUNT to count chunks(usually 4 bytes) instead of bits.

1
def count_islands(x: int):
2
    x = x & ~(x << 1)
3
    return x.bit_count()

A Different Approach

Another direction we could have taken was to focus on changing the loop. In the trivial solution we are going bit by bit, but could we change that somehow? Byte by byte? No. Island by island.

1
def count_islands(x: int):
2
    count = 0
3
    while x != 0:
4
        y = x | (x - 1)
5
        x = y & (y + 1)
6
        count = count + 1
7
    return count

So again, a lot of it is very similar. We just have two lines of code that do some magic. In simple words these the first line jumps to and island and the second one erases it. To get the number of islands we just count the amount of islands we erased. Each loop is one erase so counting the number of loop we get the number of islands.

Now, more technically, the first step takes advantage of how decrement works in binary representation.

We can see with these two examples that subtraction takes the leftmost one, converts it to zero, and converts all the following zeros to ones. Then, when we combine this with the initial input, we get all the leftmost zeros removed. So the first step converts all the zeroes after the leftmost island to ones.

Similarly to the first step, the second step takes advantage of how increment works in binary representation.

With the addition we are doing the reverse of subtraction. We are removing converting all the leftmost ones to zeros, and converting a single leftmost zero to one. Then we are masking this with the initial input to get the island completely removed. This is possible because islands must have at least one zero between then, so by performing the addition we are guaranteed that the resulting one will overlap a zero from the initial input.

Altogether, the first step increases the leftmost island to fill all the least significant bits, and the second step takes the advantage of masked increment to completely remove the leftmost island. Then this is performed in a loop until all the islands are removed, in other words, until the number is zero.

Conclusion

With this post I wanted to show how even a simple problem can be improved in different ways. Just by looking at a problem from a different lens we can get useful insights. Changing how we think about a problem can put us in a position where good solutions are easy to spot and simple to execute.