# Positive and negative integers in binary

# Binary factorization theorem: every non-negative integer can be represented
# as a binary number: 2**a + 2**b + 2**c ... 
# Inductive proof: holds for 0 and 1== 2**0.
# Assume true for all numbers 0 .. n, need to show also holds for n+1:
# 1. if n is an even number then there is no 2**0 power in the series, so
# the representation is n + 2**0 = n+1
# 2. if n is an odd number, then n+1 is an even number, therefore, by
# assumption (inductive hypothesis) (n+1)/2 has a binary factorization
#: (n+1)/2 = 2**a + 2**b + 2**c ... Therefore, n+1 = 
# 2*(2**a + 2**b + 2**c...) = 2**(a+1) + 2**(b+1) + 2**(c+1)...
# for example, if n is 9 then n+1 ==2 = 2*5.  : *=2 is left shift.

def binfactors(n):  # return array of binary factors of natural number n:
   FCT = [] # array of factors
   f = 1  # factor value start with 2**0
   while n>0:
     if n%2==1: FCT.append(f)
     n = n/2  # right shift
     f = f*2  # next bit has twice factor value
   #
   return FCT
#binfactors

print binfactors(147)

# given integer n, convert to binary (as a string so it can be printed):
# strategy: determine last bit, then keep shifting right.
# add leading zeros
def binstring(n,digits=-1):
  s = "" # string to be constructed backwards
  while n>0:
    bit = n%2  # 0 or 1
    s = str(bit) + s
    n = n/2
  #
  # add leading zeros if necessary
  while len(s)<digits:
      s = '0'+s
  return s
#binstring

print binstring(147,16)

#### inverse: convert binary string to non-negative integer

def bintonat(s):
  value = 1  # value of bit, initially 2**0
  i = len(s)-1  # start with last bit
  ax = 0     # sum of digits
  while i>=0:
    if s[i]=='1': ax += value
    value = value *2
    i -= 1
  #while
  return ax
#bintoint

print bintonat("01101")


#### negative numbers:   two's complement
#### -n = inv(n) + 1

def inv(s): #bitwise invert a binary string
  sinv = ""
  i = 0
  while i<len(s):
    if s[i]=='0': sinv = sinv + "1"
    else: sinv = sinv+"0"
    i += 1
  return sinv
#inv

# note -3 is inv(2), -4, is inv(3)... because:
# -(n-1) = inv(n-1)+1, therefore, -n = inv(n-1)

def tcstring(n,bits=-1):
  if n>=0: return binstring(n,bits)
  s = inv(binstring(-1*n-1))
  while s[0]=='0' or len(s)<bits:
     s = "1"+s
  return s
#tcstring

print tcstring(-3)
print tcstring(-10)

# two's complement binary string to int.
# Know that inv(s) is n-1, so -n = -(sn+1) where sn is inv(s) converted to nat.
def bintoint(s):
  if s[0]=='0': return bintonat(s)
  # assume 1 - deal with errors later
  nm1 = bintonat(inv(s))  # n-1
  return -1*(nm1+1)
#bintoint

print bintoint("10110")
print bintoint(tcstring(-56))


##################################  HEXIDECIMALS ###################

# hexint convertes hexidecimal string to integer value: "af" = 175
def hexint(s):
    ax = 0  # number to be returned
    power = 0
    i = len(s)-1
    while i>=0:
        
        ai = ord(s[i])
        if ai>=ord('a') and ai<=ord('f'): ai -= 32  # lower case to upper
        if ai>=ord('0') and ai<=ord('9'): val = ai-ord('0') # value of digit
        else:
            if ai>=ord('A') and ai<=ord('F'): val = ai-ord('A')+10
            else: raise Exception("bad input string")
        ax += val*(16**power)
        power += 1
        i -= 1
    # while i
    return ax
#hexint
print hexint("1a")

# convert (positive) base-10 integer to hexidecimal string.
def inthex(n): # convert n to hexidecimal string
    DIGIT = "0123456789ABCDEF"
    ax = ""  # string to be constructed
    while n>0:
        val = n%16
        ax = DIGIT[val] + ax
        n = n/16
    # while
    return ax
#inthex

print inthex(26)

# convert binary string to hex string: use "functional composition":
def binhex(s):
    return inthex(bintoint(s))
# binhex
print binhex("10011101")