Elements of programming interviews in Python problems

EPI_python Data Structures and Algorithms.py

# Elements of programming interviews in Python
# P1. Data Structures and Algorithms
# Mayra Castrosqui

######################################
# # ch1 primitive types. 
# - all should be O(1) 
# - to remember: ~(x-1) = -x
######################################

def right_prop(x):
  '''right propagate the rightmost set bit in x. 
  eg. 01010000 to 01011111
  '''
  #print(x, '=',format(x, 'b'))
  last = x & ~(x-1) # last 1
  mask = last-1
  result = x | mask
  return result

def is_powerof2(x):
  '''test if x is a power of two'''
  return x == x&-x

def module_powerof2(x, p):
  '''compute x modulo a power of two, 
  eg. 77 mod 64 return 13
  '''
  # x mod p, when p is power of 2
  assert is_powerof2(p), f'p variable must be a power of 2: {p}'
  return x & (p -1)