"""
Python functions for MAT 3670, lab 3.
"""

def bitPopulation(A):
    """
    bitPopulation(A) reports the number of bits in A which are set to one.
    """

    # Establish a counter
    count = 0

    # Iterate over all bits of A
    for i in range(len(A)):
        if A[i] == 1:
            # Another one bit has been seen, so we count it
            count = count + 1
			
    # Hand back the result
    return count


def successor(A):
    """
    successor(A) returns the binary successor of a given bit string A.
    """
    # STUB: TO BE COMPLETED


def complement(A):
    """
    complement(A) returns the bit string obtained by complementing each bit of A.
    """
    # STUB: TO BE COMPLETED


def twosComplement(A):
    """
    twosComplement(A) computes the two's complement of a given bit string A
    """
    # STUB: TO BE COMPLETED


def decimalToUnsigned(n, m):
    """
    decimalToUnsigned(n, m) produces a list of the m bits corresponding
    to the decimal value n, assumed to be non-negative.  If m is too small, 
    then the fewest possible number of bits is used.  The resulting list 
    of bits is treated as an unsigned value.
    """
    # STUB: TO BE COMPLETED


def signedToDecimal(A):
    """
    signedToDecimal(A) yields the numerical value corresponding to A,
    a list of binary digits, represented in two's complement form.
    """
    # STUB: TO BE COMPLETED


def unsignedToDecimal(A):
    """
    unsignedToDecimal(A) yields the numerical value corresponding to A,
    a list of binary digits, represented as an unsigned value.
    """

    # Process the bits in A from left to right, from most significant to least significant
    value = 0
    for i in range(len(A)):
        value = 2*value + A[i]

    return value


def add(A, B):
    """
    Performs binary addition on the bit strings A and B, yielding
    the sum.  Assumes both arguments have the same number of bits.
    """
    # STUB: TO BE COMPLETED


def subtract(A, B):
    """
    subtract(A, B) performs the subtraction A - B.  Assumes both arguments have the
    same number of bits.
    """
    # STUB: TO BE COMPLETED


def generateAllBitPatterns(n):
    """
    generateAllBitPattern(n) returns a list of all possible bit patterns of n bits each.
    """

    return [decimalToUnsigned(i, n) for i in range(2**n)]


def successorDemo(n):
    """
    Uses the successor function to cycle through all possible bit patterns of n bits
    """

    # start with the pattern of n 0's
    p = n * [0]

    # cycle through all bit patterns
    for i in range(1 + 2**n):
        print p
        p = successor(p)


def complementDemo(n):
    """
    complementDemo(n) outputs the complement of each bit pattern of n bits.
    """

    for p in generateAllBitPatterns(n):
        # get the complement of p and display the result
        pc = complement(p)
        print p, pc


def twosComplementDemo(n):
    """
    twosComplementDemo(n) demonstrates the property that, for every possible bit 
    pattern p of n bits, p + twosComplement(p) = 0.
    """

    for p in generateAllBitPatterns(n):
        # get the two's complement representation for p
        tp = twosComplement(p)

        # what happens when we add p to tp, ignoring the carry out from the MSB?
        sum = add(p, tp)

        # display the results for this bit pattern
        print p, tp, sum


def numberDemo(n):
    """
    numberDemo(n) tabulates all possible bit patterns using n bits, showing both 
    unsigned and signed values, assuming the two's complement system is used for 
    signed values.
    """

    for p in generateAllBitPatterns(n):
        print p, unsignedToDecimal(p), signedToDecimal(p)


def addDemo(n):
    """
    addDemo(n) tabulates all possible pairs of n bit quantities, performs addition 
    on each pair, and summarizes the results, both as bit strings and also as signed 
    decimal values.
    """

    # Generate all bit patterns of n bits each
    allBitPatterns = generateAllBitPatterns(n)
	
    # Generate all pairs of such bit patterns
    for p in allBitPatterns:
        for q in allBitPatterns:
            # Add the pair
            sum = add(p, q)

            # Convert to signed, decimal values
            pD = signedToDecimal(p)
            qD = signedToDecimal(q)
            sumD = signedToDecimal(sum)

            # Display a summary
            print p, "+", q, "=", sum, "or", pD, "+", qD, "=", sumD


def subtractDemo(n):
    """
    subtractDemo(n) tabulates all possible pairs of n bit quantities, performs subtraction 
    on each pair, and summarizes the results, both as bit strings and also as signed 
    decimal values.
    """

    # Generate all bit patterns of n bits each
    allBitPatterns = generateAllBitPatterns(n)
	
    # Generate all pairs of such bit patterns
    for p in allBitPatterns:
        for q in allBitPatterns:
            # Perform the subtraction
            diff = subtract(p, q)
            
            # Convert to signed, decimal values
            pD = signedToDecimal(p)
            qD = signedToDecimal(q)
            diffD = signedToDecimal(diff)

            # Display a summary
            print p, "-", q, "=", diff, "or", pD, "-", qD, "=", diffD