Section 7.5

Learning Goals

• DAT-1B: Students will explain the consequences of using bits to represent data. 

• DAT-1.C.b: Students will compare and order binary numbers. 

• Students will demonstrate that bits can represent numbers. 

• DAT-1.A.6: Bits are grouped to represent abstractions. These abstractions include, but are not limited to, numbers, characters, and color. 

• DAT-1.B.1: In many programming languages, integers are represented by a fixed number of bits, which limits the range of integer values and mathematical operations on those values. This limitation can result in overflow or other errors. 

• DAT-1.B.2: Other programming languages provide an abstraction through which the size of representable integers is limited only by the size of the computer's memory; this is the case for the language defined in the exam reference sheet. 

• DAT-1B.3: In programming languages, the fixed number of bits used to represent real numbers limits the range and mathematical operations on these values; this limitation can result in round-off and other errors. Some real numbers are represented as approximations in computer storage. 

• DAT-1.C.4: As with decimal, a digit’s position in the binary sequence determines its numeric value. The numeric value is equal to the bit’s value (0 or 1) multiplied by the place value of its position.

• DAT-1.C.5: The place value of each position is determined by the base raised to the power of the position. Positions are numbered starting at the rightmost position with 0 and increasing by 1 for each subsequent position to the left.

• AAP-2.P: For binary search algorithms:

  • a. Determine the number of iterations required to find a value in a data set.

  • b. Explain the requirements necessary to complete a binary search.

• AAP-2.P.1: The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated. EXCLUSION STATEMENT (EK: AAP-2.P.1): Specific implementations of the binary search are outside the scope of the course and the AP Exam.

• AAP-2.P.2: Data must be in sorted order to use the binary search algorithm.

• AAP-2.P.3: Binary search is often more efficient than sequential/linear search when applied to sorted data.

Objectives and General Description

Bits can be grouped together to represent different types of data.  In this section, we will focus on how bits can be used to represent numbers.  They will practice their binary conversion skills by putting binary numbers in order.  Students will also learn about overflow errors.  The lesson begins with a warm up review activity in which students and their partner will take a list of binary numbers and put them in order.  The teacher will lead the students through discussion and demonstration of the relationship between the number of bits and the values that can be represented.   Hexadecimal number conversions are no longer part of the APCSP course requirements.  However, we have included an optional  hexadecimal activity to illustrate another number system representation.

Activities

Activity 7.5.1 (10 minutes)

1. Student and partner begin to work on the Bits, Bytes, and Binary Worksheet.  Answer as many questions as possible and then fill in the rest with the class discussion in the next activity.

2. Teacher key for question one.

3. Discussion points:

   • How did you solve this?  Most will say that they converted to decimal and then put in order.  However, other students may have different methods and it is beneficial to have them share.

   • Do you need the leading zeros (on the left)?  Will removing them change the value?  Could that have sped up the process?

Activity 7.5.2 (budget 15 minutes)

1. Display the binary flippy do from Section 4.4.  . Pose the following question to students and give 1 - 2 minutes for them to silently think about it:

   1.  “What is the relationship between the binary flippy do and a byte?”

   2. The “binary flippy do” tool can represent 8 bits or a byte.  

   3. Then ask…if I have a byte, what is the largest decimal value that I can store in it?  Answer:  255  If all 8 its were 1’s, the decimal equivalent would be 255.  

   4. How many different decimal values can a byte store? Answer:   256 values, range 0 - 255. 

   5. What if I only have 6 bits?  What is the largest value?  Answer:  63

   6. If I have 6 bits, how many values can be stored?  Answer:  64 values, range of 0 - 63

2. Ask students a few more questions like those in the previous step.  Students can use their own flippy-do tools to answer.  

3. Now that students are comfortable with the relationship between the number of bits & largest decimal value or number of values, pose this question…

   1. Assume that I have a byte of storage (8 bits).  I need to store the value 256.  Can I do it?

   2. Answer:  No, I will need one more bit.

   3. If I add another bit so that I can store the value 256, what happens to the binary values stored in the original byte?  

   4. Answer:  They look like all zeros.  Think about a car odometer.  If I am at 999 miles and I go one further, the odometer rolls over to 1000.  The first three place value holders are all zeros and an additional place value has been added for the 1.  In computer storage capacity, 255 in binary is 11111111.  When we want to go to one higher (256), it “rolls over” to look like:  100000000.  The first 8 place value holders (the byte) are all zeros so is this a value of 0 for the byte or does the computer know to include the extra bit and have a value of 256?  This concept is call the “overflow error” and it results when there is a fixed number of bits to store a value.  This is all the students need to know for the scope of this content in APCSP.  Different operating systems handle this situation differently but our students are not expected to know the details of how this works.

   5. To reinforce the concepts above, assign College Board Video 2.1 Daily Video Binary Numbers in AP Classroom or play the video for the class.

4. There are additional practice questions on these topics in the secure practice exams in the AP course audit.  

Activity 7.5.3 (20 minutes)

1. Navigate to AP Classroom to watch 3.11:  Daily video 1, "Binary Search."  Have students complete this Binary Search worksheet.  Pause the video at 8:12 and have the students answer the first three questions.  Start the video again and pause again at 9:02 and have students answer questions 4 and 5.  The answers to the five problems appear in the video.

Activity 7.5.4 (budget 15 minutes)

1.  Hexadecimal conversions are no longer a required element in APCSP.  However, understanding that the conversions process algorithm is the same for differing number systems is a good skill for students to have.  They just need to know the base of the number system.  Then they can set up a place value chart and go through the same process for conversions.

2. Hexadecimal is a base 16 number system.  It uses the digits 0 - 9 and the letters A - F.  It allows much larger values to be represented.  Common uses for hexadecimal values are color values (#FFFFFF is white and #000000 is black.  All other color values fall between) and the IPv6 addressing system for IP addresses.  

3. Follow this lesson to introduce students to hexadecimal conversions.

4. Comparing Number Systems Handout for students

Resources

• 7.5.1: Bits, Bytes, and Binary (student resource)

• 7.5.1: Bits, Bytes, and Binary KEY (teacher resource)

• 7.5.3: Binary Search Worksheet student resource)

• 7.5.4: Hexadecimal Lesson Plan (teacher resource)

• 7.5.4: Comparing Number Systems Handout (student resource)