Much as I love bit hacks, I don’t think they make good phone screen questions. All but the most basic ones are just too dependent on coming up with the right “trick” in time. I am curious whether I could create a more reliable test by asking the candidate to explain, rather than develop, a short snippet of code. For example, I might ask about the following snippet of Python.

def f(n):
  for i in [1,2,4,8,16]:
    n |= n >> i
  return n + 1

What does this code do? In order to figure it out, a candidate would need to:

  1. Keep straight i vs n.

  2. Find good test cases (0 and 1 are not very illuminating, for example).

  3. Keep track of the state of n through each step of the loop.

  4. Form some idea of what the function does, either by pure logical reasoning or by generalizing their test cases.

  5. Figure out why the function works and its limitations.

Some of these tasks may sound trivial, but for many candidates they are not. Just getting a candidate to mentally step through the code with some example input can be a challenge. I am excited to try it out on my co-workers in front of a whiteboard.

Spoiler: here’s the code from which I took this question.

import math

def nextPowTwo(n):
  """Given an integer n, return the smallest power of 2 larger than n.
  n: an integer such that 0 <= n <= 2 ** 31 - 1
  examples: nextPowTwo(56) -> 64, nextPowTwo(128) -> 256
  """

  if n >> 31:
    raise ValueError("Number is too big, or negative")

  # Each iteration doubles the size of each "cluster of" 1 bits, so
  # 10001000 -> 11001100 -> 11111111
  # Until the number becomes all 1s after the first 1 bit
  for i in [1,2,4,8,16]:
    n |= n >> i

  # 00011111 + 1 -> 00100000 (i.e. the next power of two)
  return n + 1


def test(n):
  assert nextPowTwo(n) == 2**(1 + math.floor(math.log(n, 2)))
  print("nextPowTwo({}) == {}".format(n, nextPowTwo(n)))


for n in [1,2,3,4,5,6,7,8,9,13,16,393938,2147483646,2147483647]:
  test(n)