Lab 5: Binary representation of data

Creating the necessary folder

Create a subfolder called lab5 within your cs111 folder, and put all of the files for this lab in that folder.

Task 1: check your understanding of key concepts

The TA will guide you through a brief problem-solving exercise that you will complete on paper. It is designed to help you see how well you’ve mastered the key concepts from Problem Sets 2 and 3.

Note that the exams will also be paper-only, so it’s important that you are able to solve problems without relying on Spyder, on online resources, or on too much help from other people.

Task 2: recursive processing of binary numbers

In Problem Set 4, you will write recursive functions that manipulate binary numbers that are represented as strings.

The bitwise OR of two binary numbers is formed by considering the bits in the numbers from right to left. As you do so, each pair of corresponding bits is ORed together to produce the appropriate bit for the result.

For example, to obtain the bitwise OR of 10100 and 00101, we would begin by essentially lining up the two numbers as follows:

10100
00101
-----

We would then OR together each pair/column of bits from right to left. For example, the rightmost column gives us (0 OR 1) which is 1:

10100
00101
-----
    1

The next pair/column of bits gives us (0 OR 0) which is 0:

10100
00101
-----
   01

Continuing in this way, we get:

10100
00101
-----
10101

And thus the bitwise OR of 10100 and 00101 is 10101.

If one number has more bits than the other, the extra bits are effectively ORed with 0s, and thus they are unchanged in the result. For example:

10101010
   11000
--------
10111010

In Spyder, open a new editor window using File -> New File, and save it to your lab5 folder using the name lab5.py.

Write a function called bitwise_or(b1, b2) that takes as inputs two strings b1 and b2 that represent binary numbers. The function should use recursion to compute the bitwise OR of the two numbers, and return the result in the form of a string. For example:

>>> bitwise_or('10100', '00101')
result: '10101'

>>> bitwise_or('10101010', '11000')
result: '10111010'

Notes/hints:

• Base cases: Because the function will be called recursively on smaller and smaller strings, you will eventually get down to an empty string for one or both of the inputs.

  • If both inputs are the empty string, the function should return the empty string.

  • If only one of the inputs is the empty string, the function should return a string that represents the result of ORing the other input with 0s.

  For example:

  >>> bitwise_or('', '')
  result: ''
  
  >>> bitwise_or('101', '')
  result: '101'
  
  >>> bitwise_or('', '11010')
  result: '11010'
  

• You should use recursion to compute the bitwise OR of the rest of the bits in the two numbers. When you do so, make sure that you end up considering the bits from right to left, rather than from left to right.

• As usual, we recommend making the recursive call at the start of the recursive case and storing its return value in a variable. Then you can use that variable to construct the value that you will return.

• You will need to use conditional execution (if-elif-else) to decide what to return, based on the bits that are being ORed by the current call of the function. Use concrete cases as needed to figure out the logic.

Task 3: non-recursive processing of binary numbers

In lecture, we discussed the left-shift and right-shift operators.

Based on your understanding of how those operators work, add the non-recursive functions described below to your lab5.py file. Feel free to ask one of the staff members for help.

1. Write a function left_shift(b, n) that takes as inputs a string b that represents a binary number and an integer n, and that returns the result of performing a left shift of b by n places. For example:

   >>> left_shift('10101', 3)
   result: '10101000'
   
   >>> left_shift('10101', 5)
   result: '1010100000'
   

   If n is 0 or negative, the function should return the original bitstring:

   >>> left_shift('10101', -3)
   result: '10101'
   
   >>> left_shift('10101', 0)
   result: '10101'
   

   Remember: The functions for this task do not need to use recursion!

2. Write a function right_shift(b, n) that takes as inputs a string b that represents a binary number and an integer n, and that returns the result of performing a right shift of b by n places. For example:

   >>> right_shift('10111', 1)
   result: '1011'
   
   >>> right_shift('10111', 3)
   result: '10'
   

   If n is 0 or negative, the function should return the original bitstring, just as left_shift does.

   In addition, if n is greater than or equal to the number of bits in the original string, the function should return the string representation of 0:

   >>> right_shift('10111', 5)
   result: '0'
   
   >>> right_shift('10111', 8)
   result: '0'
   

Optional extra practice: representation of integers; binary addition

In lecture, you have seen how we can represent numbers in base two (binary) and base ten (decimal). For example, we can represent the decimal number 21 as 10101 in binary, and the decimal number 7 as 111 in binary.

Complete the following exercises for extra practice:

1. Convert the decimal number 44 to binary.
2. Convert the decimal number 35 to binary.
3. Convert the binary number 100111 to decimal.
4. Convert the binary number 10000 to decimal.
5. Add the binary numbers 10110 and 1101. Use the “elementary-school addition” approach that was discussed in lecture.

If you have extra time!

Review the midterm 1 info sheet and do some of the practice problems that it provides.

Last updated on October 7, 2024.