When I interview someone, I usually ask at least one bit-shifting question to

the candidate. It’s not a dealbreaker if she fails to answer it, but it

certainly wins her a lot of points if she can, or at least discuss

it in convincing ways.

Interestingly, pretty much every single candidate that I have ever

interviewed who did well on the other questions that I asked (typically at a

higher-level, such as OO design or design pattern) also does well on the

bit-shifting question, so it’s usually a pretty strong indicator of someone who

has a good computer science background overall.

There are three categories of bit-shifting questions that I usually pick

from, in increasing order of difficulty:

- How can you determine if a number is a power of two?
- How can you clear the rightmost bit?
- How can you count the number of 1 bits?

This last question is a classic, so I added my own personal twist to it (see

below).

Let’s take them in turn.

**1. How can you determine if a number is a power of two?**

The easiest way to answer this question is to notice that a power of two

has exactly one 1 followed by only zero’s (except for 1, which is also covered by the following

solution). Therefore, the quickest way is probably:

return x != 0 && (x & (x-1)) == 0;

The idea is that subtracting one from such a number will flip all its bits:

the 1 becomes a 0 and all the zeros become 1. "and"ing these two numbers

will therefore equal to zero.

As far as I can tell, this only happens for powers of two: if the

number has any other 1 than the one we are interested in, it will not be flipped

by the subtraction and will therefore survive the &.

I will accept any variations thereof: at this point, I am just trying to see

if the candidate has any notion of binary coding.

**2. How can you clear the rightmost bit?**

There are several ways to answer this question and ideally, the candidate

will start by giving me the easiest one and then, the bit-oriented one when

pressed. You can simply observe that clearing the rightmost bit is a no-op

is the number is even and a decrement of the number if it is odd:

return (n % 2 == 0 ? n : (n - 1))

This is not very efficient so I will ask for a faster solutions. There are

a couple of options:

return n - (n & 1)

or

(n >> 1) << 1

This last solution is mine, and I prefer it over the others because shifting

is much faster than subtracting. If the candidate doesn’t provide it, I

will usually suggest it and ask her to discuss the pros and cons of each.

**3. How can you count the number of 1 bits?**

And finally, we reach this timeless classic. If the candidate

has never heard of it, she’s in for a tough time. And even if she does, I

have my own twist to it that guarantees me that I will get to take a close look

at the way she thinks.

Let’s start with the naive solution: shift the number right and

increment a counter each time the rightmost bit is 1:

int counter = 0; while (n > 0) { if (n % 2 == 1) counter++; n >>= 1; }

Next comes the leap of faith: "This algorithm executes p times, where p is

the size in bits of n. Can you think of a solution that executes in b

times, where b is the number of 1 bits in n?".

Either she knows the answer or

she doesn’t, and if she doesn’t, she’ll be stumped. At this point, I will

step in and I will give her a hint: "Can you describe to me what the

expression *n & (n-1)* does to n?".

If you’ve never seen this trick, it’s impossible to answer right away:

you will need to apply the formula on the board on a few numbers before you put

the pieces together (which is already not very easy). The answer is:

"It clears the rightmost 1 bit in n".

With this in mind, the solution to the puzzle becomes:

int counter = 0; while (n != 0) { counter++; n = n & (n-1); }

If she gave me this answer without help, I will strongly suspect that she

already knew the trick, so I will throw in my own twist: "Can you

demonstrate that *n & (n-1)* clears the rightmost bit?".

And I will leave

this as an exercise to the reader for now. Answer in a few days.