Interview Prep: More on Bit Manipulation

Welcome back again to another episode of Interview Prep. We’ve been playing around with Bit Manipulation lately. If you didn’t catch my first article the gives the basics, give it a quick read-through now as we’ll be continuing on from where it left off:

Bitwise Manipulation, Part I

As a quick overview, remember that “bit manipulation” means we’re working in base-2 instead of base-10. The reason why we care is that working in base-2 gives us a finer level of control over our data. Think of bit manipulation as working with a nail file instead of a hammer.

So now that you know some basic operations of bit manipulation from my first article, let’s use those operations to do some cool stuff and also to help us answer some possible interview questions.

Clear the Least Significant Bit that is Set

The question you might get goes like this:

“Clear the least significant set bit in a given
sequence of bits”

First, let’s define the terms. What do they mean by “significant” bit?

Simple. Look at this sequence of bits:

                                          X
1010001110000001000000010000111100000101010

Now put your finger on the screen (go ahead, I won’t tell!) on the extreme right side of the sequence(Marked with an “X”). Now move your finger along the sequence to the left.

You are now moving your finger from the least significant bit toward the more significant bits.

<<---<<<<---<<<<<go to the left to get more significant

                                          X
1010001110000001000000010000111100000101010
Y

In our example, the bit marked with an “X” is the least significant and “Y” is the most significant bit. The degree
of “significance” increases as we move our finger along the bit sequence from right to left.

Now back to our original question. Let’s take a fresh bit sequence:

We are being asked to create an algorithm that clears the least significant set bit.

If we put our finger on the extreme right side of the sequence( cell E3), we move our finger to the left along the sequence and there move from least “significant” bit to more significant bit. The first set bit we come to is the “1” in cell D1 marked in red. This is the bit we need to clear and turn into a zero.

In our algorithm, we have two basic tasks to perform: 1) find the least significant set bit and then “clear” it, meaning set it to zero.

Now comes the cool part. The easy way we can find and clear the least significant bit is to use bit manipulation. And here’s the formula that works every time for this problem:

 x & ( x - 1)

Let’s just work out the above formula!

We were given “x” :

Now let’s type in x-1 on line 5:

Lastly, let’s find out what the expression x & (x-1) resolves to:

Just to review our “&” operation:

In Column A: “1” on line 3 and “1” on line 5 resolve to “1” on line 8.

Column B: 0 and 0 resolve to 0

Column C: 1 and 1 resolve to 1

Column D: 1 and 0 resolve to 0

Column E: 0 and 1 resolve to 0

Remember we wanted to find and clear the least significant bit in line 3, the bit marked in red. And that’s what we did! In line 8, we see Cell D8 marked in blue where the cell was cleared.

Our secret formula: x & ( x-1) cleared the least significant bit.

One More

Let’s look at one more problem. Given a sequence of

bits(we’ll start with the same one we’ve been using)

We’re asked to write an algorithm that sets the least significant cleared bit.

In the image above, we’re given the sequence on line 3.
The least significant cleared bit is in cell E3. We want our algorithm to choose this cell and set it so that we’re left with the bit sequence on line 8.

How do we do it?

Simple! We’ll use another magic bit manipulation formula. This time, it’s:

          x | (x + 1)

Let’s do it!

We already have “x”, so let’s fill in (x + 1) on line 5 below and then let’s check to see that it resolves to our desired result on line 8:

We see that we successfully found the least significant cleared bit in our given sequence (Cell E3) and set it in our result in Cell E8 (in red) on line 8. Voilà!

Those are just a couple of tricks. There are more, so I hope that whets your appetite and increases your appreciation for bit manipulation. This way of looking at numbers allows us to make some subtle changes in our values that would otherwise not be possible.

Keep coding out your dreams!