*Python 3 Question*

In class, we discussed binary representation and how to convert a positive integer value from base 10 (decimal) into base 2 (binary) (or any other base) through repeated division. The pseudocode algorithm (for any base up through 16) is as follows:

Set digits to "0123456789ABCDEF" (extend this with more letters for bigger bases, up to 36)

Set value to starting base 10 value

Set base to desired base (e.g., 2 for base 2)

Set answer to "" (the empty string)

While value is greater than 0:

Set remainder to value % base

Set answer to digits[remainder] + answer

Set value to value // base

For example, translating 35 (base 10) into base 5 would work as follows:

35 5 = 7, remainder 0, so value becomes 7 and answer becomes "0"

7 5 = 1, remainder 2, so value becomes 1 and answer becomes "20"

1 5 = 0, remainder 1, so value becomes 0 and answer becomes "120"

Upon reaching 0, we stop the division process, so the final answer is 120 (base 5).

Follow the steps below to complete a Python program that (a) translates any base 10 number into a user-specified base (up through base 16), and (b) builds on that function to translate any base 10 integer (positive or negative) into a special form of binary representation called two's complement. See the end of the lab write-up for some test cases to verify that your functions work correctly.

1. Converting Base 10 Into Any Other Base

Complete the changeBase() function in the provided starter program by writing Python code that reproduces the pseudocode algorithm above. This function takes two arguments: a positive base 10 number, and an integer (representing the new base) in the range 116 (inclusive); it returns the equivalent value in the new base. Your function should return its final answer (the converted value) as a string, in case the new base is greater than 10.

DO NOT simply print out the result!

Note: The pseudocode algorithm given above assumes that the initial number is greater than 0. If it is exactly 0, then its value in the new base is 0 as well (the algorithm above doesn't account for this special case, but you should).

2. Two's Complement

The binary representation that we discussed in lecture assumes that we are only dealing with positive integers. In the real world, however, we need to handle negative integer values (e.g., -5) as well. To get around this limitation, modern computers use a variation of binary called two's complement representation. Two's complement allows us to represent both positive and negative numbers in binary, with the leftmost bit serving as the sign bit (if the sign bit is 0, then the number is positive (or 0); if the sign bit is 1, then the number is negative). Two's complement isn't as simple as simply sticking a sign bit at the beginning of a binary value, though; the presence and interpretation of the sign bit also affects many of the other bits in the number (meaning that the binary representations for +5 and -5 look very different from one another). For example, the 4-bit-long representation of +5 in two's complement is 0101 (+5 in regular binary is 101; we add a leading 0 to emphasize that the value is positive). The 4-bit-long two's complement representation of -5 is 1011, however (the leading 1 indicates that the value is negative, but notice that the last 3 bits have changed from 101 to 011).

Two's complement values are also fixed in length at the time that they are created; the same negative number may have multiple (slightly different) two's complement representations based on its final length in bits. For example, the 4-bit-long two's complement representation of -5 is 1011, while the 8-bit-long two's complement representation of -5 is 11111011. If you look closely, there's a trick to this: in order to get the longer (more bits) version of the number, we simply extended (duplicated) the first (sign) bit to reach the desired length.

Follow the steps below to complete the twosComplement() function from the starter code. This function takes two arguments: a base 10 number to translate, and an integer length for the result (assume that this length will always be big enough to accommodate the original value). The function returns the two's complement version of the original number as a string.

a. If the original value is greater than or equal to 0, then the two's complement conversion process is extremely simple: translate the original value into binary (base 2) normally, and then "pad" or extend the answer with leading 0s until it meets the desired length.

Use changeBase()

(from Part 1) to perform the initial translation, and then use a while loop to keep adding '0' characters, one at a time, to the beginning of the result until it reaches the length specified by the user (as the second parameter).

For example, twosComplement(25, 8) first converts 25 into base 2, getting the string "11001". This string is only 5 characters long, not 8, so we add three '0' characters to the beginning to get "00011001" as our final answer.

b. If the original value is negative, then we need to add a few more steps in order to produce the two's complement representation:

i. Convert the absolute value of the original number into base 2 and pad it, like you would have done in Step 2.a. For example, if the original value was -38, convert (positive) 38 to base 2 and pad the result to the desired length. Use Python's built-in abs() function, or multiply the value by -1, before calling changeBase().

ii. Now we need to negate our binary string value to make its value negative again. Start by inverting every bit; each '0' becomes '1', and each '1' becomes '0'. One way to do this is to use a loop to build a new string, one character at a time, based on the content of the original binary string. A more efficient solution uses the Python string operation replace() (with a placeholder value) to swap 0s and 1s:

inverted = binary.replace('0', '2') # change old 0s to 2s

inverted = inverted.replace('1', '0') # replace old 1s with 0s

inverted = inverted.replace('2', '1') # change 2s back to 1s

iii. The final step of the negation process is to add 1 to the inverted value using binary addition. Binary addition isn't terribly complicated, but we will use a (very) simplified equivalent to keep this assignment's length under control. The last '0' in the number changes to '1', and every digit to its right (which must be '1', by definition) changes to '0'. Every digit before (to the left of) the last '0' stays the same. For example, "110010" will become "110011". "100111" will become "101000". "101101" will become "101110".

Perform this operation as follows:

1. Use Python's list() function to change your binary string into a list of one- character strings. For example, list('1101') returns ['1','1','0','1'].

2. Use a while loop to examine the resulting list from the last element (index length -1) to the first element. While the index is greater than or equal to 0 and the element at the current index is '1', change that element to '0' and subtract 1 from the index to keep moving toward the front of the list.

3. When the loop ends, if the index is greater than -1, change that element to '1'.

4. Use join() and the empty string to restore your list to a single string: answer = "".join(myList)

3. After completely finishing Step 2(a) or Step 2(b), return your final result (a string of 0s and 1s whose length matches the second function parameter).

Here is the required starter code for this question:

def changeBase(value, newBase): answer = '' # ADD YOUR CODE HERE

return answer

def twosComplement(value, length): answer = '' # ADD YOUR CODE HERE

return answer

---------Do not change code below----------

if __name__ == "__main__": start = int(input("Enter a base 10 value to convert: ")) b = int(input("Enter the new base as an integer between 1 and 16: "))

converted = changeBase(start, b) print(start, "(base 10) is", converted, "in base", b) print()

original = int(input("Enter a base 10 integer to convert to two's complement: ")) numBits = int(input("How many bits long should the output be? "))

tc = twosComplement(original, numBits) print(original, " (base 10) is ", tc, " in ", numBits, "-bit two's complement representation.", sep='') # removed inter-part spaces for formatting purposes print()

Test Cases for Part 1 (the changeBase() function) 28 (base 10) is 1C in base 16 294 (base 10) is 446 in base 8 . 37 (base 10) is 100101 in base 2 9(base 10) is 3 in base 4 Test Cases for Part 2 (the twoscomplement () function) . 13 (base 10) is 00001101 in 8-bit two's complement . 0 (base 10) is 00000 in 5-bit two's complement Test Cases for Part 1 (the changeBase() function) 28 (base 10) is 1C in base 16 294 (base 10) is 446 in base 8 . 37 (base 10) is 100101 in base 2 9(base 10) is 3 in base 4 Test Cases for Part 2 (the twoscomplement () function) . 13 (base 10) is 00001101 in 8-bit two's complement . 0 (base 10) is 00000 in 5-bit two's complement