Basic binary operations implemented in [[Python]]. Copied from the Dynamic Programming, Greedy Algorithms course at CU Boulder.
## convert to and from binary
```python
def convert_to_binary(n):
assert n >= 0
if n == 0:
return [0]
lst = []
while n > 0:
lst.append( n % 2)
n = n // 2 # Integer division in python uses //
return lst
def convert_to_decimal(lst):
sum = 0
f = 1
for elt in lst:
sum = sum + elt * f
f = f * 2
return sum
```
## add, subtract and multiply
See [[Karatsuba's multiplication algorithm]] for a faster implementation of multiply.
```python
def bitwise_add(ai, bi, ci):
if ai == 0:
if bi == 0:
return (ci, 0)
else: # ai= 0, bi = 1
return (1-ci, ci)
else:
if bi == 0:
return (1-ci, ci)
else:
return (ci, 1)
def add(a, b):
# add bit strings a, b
(n, m) = len(a), len(b)
carry = 0
c = []
for i in range(max(m,n)):
ai = a[i] if i < n else 0
bi = b[i] if i < m else 0
(ci, carry) = bitwise_add(ai, bi, carry)
c.append(ci)
if carry == 1:
c.append(carry)
return c
def subtract(a, b):
# we will use two's complement subtraction
# this is a very nice and common trick where
# we can use addition to perform subraction of
# binary numbers. It is used inside computers.
# assume a >= b -- this will generally hold for all our use cases
n = len(a)
#assert(len(b) <= n)
k = len(a) - len(b)
bcomp = [1-elt for elt in b] + [1]*k # flip the bits in b and pad with 1s
bcomp2 = add(bcomp, [1]) # add 1
r = add(a, bcomp2)
return r[0:n]
def pad(a, k):
return [0]*k + a
def grade_school_multiply(a, b):
n, m = len(a), len(b)
tmp = a
res = [0]
for bit in b:
if bit == 1:
res = add(res, tmp)
tmp = [0]+tmp # shift tmp
return res
```