Bit shifing questions and answers

From http://beust.com/weblog/, on 26 July 2004.

Fun with bits

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:

1. How can you determine if a number is a power of two?
2. How can you clear the rightmost bit?
3. 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.