Some useful bit arithmetic

add.py

#addition, full adder style
def add(a,b):
  if a == 0:
    return b
  elif b == 0:
    return a
  summed = a^b
  carry = (a&b) << 1
  return add(summed,carry)

is_2_to_the_n.py

#recursive solution
def is_a_power_of_two_recursive(n):
  if n==1: return True
  if n==0 or n%2 != 0 : return False
  return is_a_power_of_two_recursive(n/2)


#bit arithmetic solution
def is_a_power_of_two(n):
  return n != 0 and (n & (n-1)) == 0 

log2.py

#returns the floor of the log2 of n
def log2(n):
  i = -1
  while n > 0:
    n = n >> 1
    i += 1
  return i

multiply.py

def multiply(a,b):
  #check if we have a zero in the params, if we do, just return 0
  if a == 0 or b == 0:
    return 0
  #if any of the params are 1, just return the other
  if a==1:
    return b
  elif b == 1:
    return a
  #now we perform optimizations for numbers that are powers of 2
  #we always perform the shift using log2(b) if b is a power of 2, so if a is the power of 2
  #swap a and b them and mark that we know its a power of 2
  a_is_pow2 = False
  if(is_a_power_of_two(a)):
    a,b = b,a
    a_is_pow2 = True
  if(a_is_pow2 or is_a_power_of_two(b)):
    return a << log2(b)
  else:
    #we want to iterate as few times as possible, so add the larger
    #number together by the smaller number of times
    add_this_many_times,add_this = sorted([a,b])
    sum = add_this
    for i in xrange(1,add_this_many_times):
      sum = add(add_this,sum)
    return sum

assert(multiply(3,5) == 15)
assert(multiply(4,1) == 4)
assert(multiply(67,2) == 134)
assert(multiply(10,10) == 100)
assert(multiply(4,10) == 40)
assert(multiply(1024,2**4) == 16384)
assert(multiply(2**6,2**0) == 64)