### CSC 15 Class excercise:  You will find in the following several functions
### that convert numbers to and from base-10 integers, binary strings and 
### hexidecimal strings.  There is also a function to convert negative 
### base-10 integers to the two's complement binary representation.

### In two's complement arithmetic, to negate a number n to -n, we bit-wise
### invert the bits of n (1 to 0, 0 to 1), then add 1 to the result.
### This means, for example, that if we bit-wise invert -4, we should get
### the binary representation of +3. (that's a hint).

### You are to devise an algorithm, then a program, to convert two's
### complement binary strings into integers. 

### Also write a function, using functional composition, to convert a
### hexidecimal string to a base-10, possibly negative integer.

###########################

# function to convert (positive) base-10 integer to binary conversion:  
def intbin(n):  # returns a binary string such as "10110"
    if n<0: return inttwos(n,32)  # call different function if negative
    # assume n is non-negative.
    s = ""  # string to be built backwards
    while n>0:
        digit = n%2
        s = str(digit)+s # note digit added to the front of s
        n = n/2
    # while
    return s
# intbin

# inverse function: given binary string, return (non-negative) integer
def binint(s):
    ax = 0  # number to be returned
    power = 0
    i = len(s)-1
    while i>=0:
        val = ord(s[i])-ord('0')  # "0" becomes 0, 1 becomes 1
        ax += val*(2**power)
        power += 1
        i -= 1
    # while i
    return ax
# binint

# 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')
        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(binint(s))
# binhex
print binhex("10011101")

# function to convert integer to two's complement binary string
def inttwos(n,bits):
    if (n>=0): return intbin(n)
    if n< -2**(bits-1): raise Exception("not enough bits")
    m = intbin(abs(n) - 1) # binary rep of -n-1, to be subtracted from -1
    # add leading zeros to m
    m = ("0"*(bits-len(m))) + m
    # subtracting m from -1 is just a matter inverting the bits
    s = ""
    i = len(m)-1
    while i>=0:
        if m[i]=='1': s = '0'+s
        if m[i]=='0': s = '1'+s
        i -=1
    #while
    return s
# twos
print inttwos(-3,32)
print intbin(-3)   # forward reference ok in python