next_power_of_2.md

# status-quo, readability
def a_next_power_of_2(x):
    if x == 0: return 0
    return 1 if x == 1 else 2 * a_next_power_of_2((x+1)//2)

# faster version, cross-language
def b_next_power_of_2(v: int) -> int:
    """
    Get the next power of 2. (for 64 bit range ints)
    Examples:
    0 -> 0, 1 -> 1, 2 -> 2, 3 -> 4, 32 -> 32, 33 -> 64
    """
    # effectively fill the bitstring (1 less, do not want to  with ones, then increment for next power of 2.
    v -= 1
    v |= v >> (1 << 0)
    v |= v >> (1 << 1)
    v |= v >> (1 << 2)
    v |= v >> (1 << 3)
    v |= v >> (1 << 4)
    v |= v >> (1 << 5)
    v += 1
    return v

# iteration on readability, fast in python
def c_next_power_of_2(v: int) -> int:
    if v == 0: return 0
    return 1 << (v-1).bit_length()

funcs = {'a': a_next_power_of_2, 'b': b_next_power_of_2, 'c': c_next_power_of_2}
tests = [
    (0,0), (1,1), (2,2), (3,4), (31,32), (32,32), (33,64)
]
for (inp, out) in tests:
  for name, fn in funcs.items():
    res = fn(inp)
    if res != out:
      print("bad run, test: (%d, %d), got: %d, func: %s" %(inp, out, res, name))


# Far from perfect benchmarking code, but good enough to show relative performance
import time

for name, fn in funcs.items():
  print("benching ", name)
  start = time.time()
  for i in range(0, 1000000, 33):
    res = fn(i)
  end = time.time()
  print("bench", name, " took ", end - start)

No bad runs (after I added a case for 0, and adjusted the bit-length approach with -1 to match behavior).

Bench results:

benching  a
bench a  took  0.17035603523254395
benching  b
bench b  took  0.02341461181640625
benching  c
bench c  took  0.011197090148925781