We are invited to write expressions to do the each of the following in O(1) time:

  • Right propagate the rightmost set bit in x
  • Compute x mod a power of two
  • Test if x is a power of 2

Now that we have increased ability to visualize binary representations of numbers and how bitwise operations act on them we should be able to avoid too much clumsiness. The key insight lies in the difference in the representation of any x and x - 1.  With that we can produce some elegant formulations:

def right_propagate(x):
    return x | x - 1


def xmod(x, mod):
    return x & mod - 1


def ispowerof2(x):
    return x & x - 1 == 0

If we are worried about 0 masquerading as a power of 2 (as 0 & -1 == 0), we may need to guard against that input. Likewise the mod function is not at all useful for second parameters not powers of 2!