Python Exercise

Research the arange function from the Numpy library and the list and map functions.  On the Python command line, code a procedure to convert an 8-bit binary string to a base-10 integer.  Hint: With arange, generate a Numpy array that contains the powers of 2 in their correct positions.  In other words, the array will be [7, 6, 5, 4, 3, 2, 1, 0]. Use list and map together to obtain an array or list of the integers 0 and 1 that can be used in vector computations.  For example, if the binary string representation is ‘00110101’, use list and map to obtain the list (or array) [0, 0, 1, 1, 0, 1, 0, 1].  Then, using vector multiplication and exponentiation, multiply that list by powers of 2 obtained from the position array ([7, 6, 5, …]).

Vector operations in Python are quite easy.  For instance, if [7, 6, 5, …] is a Numpy array, and [0, 0, 1, 1, 0, 1, 0, 1] is a list, then:

There are multiple correct approaches to solve this problem.

>>> b = '00110101'

>>> len(b)

8

>>> blist = list(b)

>>> blist

['0', '0', '1', '1', '0', '1', '0', '1']

>>> posn = [7,6,5,4,3,2,1,0]

>>> posn = np.arange(7,0,step=-1)

>>> posn

array([7, 6, 5, 4, 3, 2, 1])

>>> posn = np.arange(8,0,step=-1) - 1

>>> posn

array([7, 6, 5, 4, 3, 2, 1, 0])

>>> bb = blist == '1'

>>> bb

False

>>> blist0 = list(map(int, blist))

>>> blist0

[0, 0, 1, 1, 0, 1, 0, 1]

>>> blist0 * posn

array([0, 0, 5, 4, 0, 2, 0, 0])

>>> blist0 * 2**posn

array([ 0,  0, 32, 16,  0,  4,  0,  1])

>>> sum(blist0 * 2**posn)

53

>>>

Floating point numbers, or non-integers, as well as negative numbers, can be expressed in a variety of ways.  There are various standards that are used by microprocessor manufacturers to represent these non-integral values.  This topic is beyond the scope of the current discussion.  However, a short discussion on representing fractions is needed.  Just as bits (having values 0 or 1) are used for integers, bits to the right of the decimal point (i.e. the fractional part) represent fractional powers of 2.  For instance, 2¹ = 2, 2⁰ = 1, and 2-1 = 1/2¹ = ½.  Similarly. 2^-2 = 1/2² = 1/4, 2^-3 = 1/2³ = 1/8, 2⁴ = 1/2⁴ = 1/16, etc.  Consequently,

0.1₂ (0.1 in binary) = 2^-1 = 1/2¹ = ½

0.01₂ = 2^-2 = 1/2² = 1/4,

0.001₂ = 2^-3 = 1/2³ = 1/8

0.0001₂ = 2⁴ = 1/2⁴ = 1/16, etc.

As was the case with integers, one can determine the base-10 representation of a fraction through sums of various powers of 2.  For example,

0.101₂ = (1 x 2^-1) + (0 x 2^-2) + (1 x 2^-3) = ½ + 0 + 1/8 = 5/8 = 0.625

0.0011₂ = (0 x 2^-1) + (0 x 2^-2) + (1 x 2^-3) + (1 x 2^-4) = 0 + 0 + 1/8 + 1/16 = 3/16 = 0.1875

The same procedure can be applied if the number has an integer part (i.e., mixed fractions).  For example,

11011.01101₂ = (1 x 2⁴) + (1 x 2³) + (0 x 2²) + (1 x 2¹) + (1 x 2⁰) + (0 x 2^-1) + (1 x 2^-2) + (1 x 2^-3) + (0 x 2^-4) + (0 x 2^-5)

= 16 + 8 + 0 + 2 + 1 + 0 + ¼ + 1/8 + 0 + 1/32

= 27 + ¼ + 1/8 + 1/32

= 27 13/32

= 27.40625

The reader may have observed that although any integer can be expressed perfectly in binary, fractional numbers can only be perfectly represented if they are sums of negative powers of 2.  For example, the very common decimal number 0.1₁₀ (0.1 in decimal, base-10 format) does not have a perfect binary representation.  In a digital computer, 0.1₁₀ can only be approximated in binary (base-2) format.  One such approximation, with 9 binary decimal places, is 0.000110011₂:

0.000110011₂ = 2^-4 + 2^-5 + 2^-8 + 2^-9 = 1/16 + 1/32 + 1/256 + 1/512 = 0.099609375₁₀ ≈ 0.1₁₀.

It is clear that most fractional numbers cannot be expressed perfectly in binary.  Very common fractions, like 1/3, 1/5, 1/20 (5%) etc. do not have a perfect binary representation.

For experimentation with mixed binary numbers, the Python function convert_mixed_binary_to_decimal is provided in the code distribution for this course.   Some examples, as well as checks implemented on the Python command line, are shown below.

>>> convert_mixed_binary_to_decimal('11011.0101011')

27.3359375

>>> ## Use an existing function to check the integral part.  Note that 8 bits are required for using this function.

>>> nint = convert_8bit_binary_to_decimal('00011011')

>>> nint

27

>>> ## Calculate the fractional part.

>>> nfrac = 1/4 + 1/16 + 1/64 + 1/128

>>> nfrac

0.3359375

>>> n = nint + nfrac

>>> n

27.3359375

>>> ## Final check....

>>> n == convert_mixed_binary_to_decimal('11011.0101011')

True

>>>

An additional, longer example follows.

>>> b = '111101010011.0111011100101'

>>> x = convert_mixed_binary_to_decimal(b)

>>> x

3923.4654541015625

>>> ## The integer part is longer than 8 bits, so the available conversion cannot be used.  However, the built-in Python function int can be employed.

>>> nint = int('111101010011', 2)

>>> nint

3923

>>> ## The fractional part will be calculated in a straightforward manner for clarity.

>>> ## Exponents (the powers) will be put into a Numpy array.

>>> powers = np.array([2, 3, 4, 6, 7, 8, 11, 13])

>>> ## Make the powers negative.

>>> powers = -powers

>>> powers

array([ -2,  -3,  -4,  -6,  -7,  -8, -11, -13])

>>> ## Sum the powers of 2.

>>> nfrac = sum(2.0 ** powers)

>>> nfrac

0.4654541015625

>>> n = nint + nfrac

>>> n

3923.4654541015625

>>> ## Final check....

>>> n == convert_mixed_binary_to_decimal(b)

True

Implementation Note:

In Python, the logical expressions used in the examples above can be defined to obtain the corresponding truth tables.  The not, and, and or operators are operators in the Python language.  The XOR operation is implemented with the ^ operator.

Example 1

>>> ## ((a AND b) OR (a XOR b)) NAND (NOT(a) NOR b)

>>> def expr1(a, b):

return not(((a and b) or (a ^ b)) and (not(not(a) or b)))

>>> for a in (False, True):

for b in (False, True):

print(expr1(a, b), " ", end="")

print()

True  True

False  True

Example 2

>>> ## NOT(NOT(a XOR (a AND B)) OR (a NOR (a AND (a XOR b))))

>>> def expr2(a, b):

res0 = not(a ^ (a and b))

res1 = not(a or (a and (a ^ b)))

return(not(res0 or res1))

>>> for a in (False, True):

for b in (False, True):

print(expr2(a, b), " ", end="")

print()

False  False

True  False

[Code Resources]

[Work Cited]