15-213 Data Lab: Twiddling Bits (Lab 1)

Please see one of us or email staff-213@cs.cmu.edu with any questions or concerns. As always, we're here to help.

Index

Dates
Introduction
Logistics
Hand Out Instructions
Evaluation
Part 1: Bit Manipulations
Part 2: Two's Complement Arithmetic
Advice
HandIn

Important Dates:

  • Assigned: Thu., Jan 17
  • Due: Tue., Jan. 29, 11:59PM

Introduction

The purpose of this assignment is to become more familiar with bit-level representations and manipulations. You'll do this by solving a series of programming "puzzles." Many of these puzzles are quite artificial, but you'll find yourself thinking much more about bits in working your way through them.

Logistics

You may work in a group of up to 2 people in solving the problems for this assignment. The only "hand-in" will be electronic. Any clarifications and revisions to the assignment will be posted on the course Web page.

Hand Out Instructions

All files you need are in the directory
/afs/cs/academic/class/15213-s02/labs/

Start by copying the file datalab-handout.tar from that directory to a (protected) directory in which you plan to do your work. Then give the command: "tar xvf datalab-handout.tar". This will cause 8 files to be unpacked into the directory: README, Makefile, bits.h, btest.h, bits.c, btest.c, decl.c, and test.c. The only file you will be modifying and turning in is bits.c. The file btest.c allows you to evaluate the functional correctness of your code. The file README contains additional documentation about btest. Use the command make btest to generate the test code and run it with the command ./btest.

Looking at the file bits.c you'll notice a C structure team into which you should insert the requested identifying information about the one or two individuals comprising your programming team. Do this right away so you don't forget.

The bits.c file also contains a skeleton for each of the 15 programming puzzles. Your assignment is to complete each function skeleton using only straightline code (i.e., no loops or conditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to use the following eight operators:

! ~ & ^ | + << >>

A few of the functions further restrict this list. See bits.c for the detailed rules.

Evaluation

Your code will be compiled with gcc and run and tested on one of the class machines. Your score will be computed out of a maximum of 75 points based on the following distribution:
  • [40] Correctness of code running on one of the class machines.
  • [30] Performance of code, based on number of operators used in each function.
  • Style points, based on your instructor's subjective evaluation of the quality of your solutions and your comments.

The 15 puzzles you must solve have been given a difficulty rating between 1 and 4, such that their weighted sum totals to 40. We will evaluate your functions using the test arguments in btest.c. You will get full credit for a puzzle if it passes all of the tests performed by btest.c, half credit if it fails one test, and no credit otherwise.

Regarding performance, our main concern at this point in the course is that you can get the right answer. However, we want to instill in you a sense of keeping things as short and simple as you can. Furthermore, some of the puzzles can be solved by brute force, but we want you to be more clever. Thus, for each function we've established a maximum number of operators that you are allowed to use for each function. This limit is very generous and is designed only to catch egregiously inefficient solutions. You will receive two points for each function that satisfies the operator limit.

Finally, we've reserved 5 points for a subjective evaluation of the style of your solutions and your commenting. Your solutions should be as clean and straightforward as possible. Your comments should be informative, but they need not be extensive.

Part I: Bit Manipulations

Name Description Rating Max Ops
bitAnd(x,y) (x&y) using only ~ and | 1 8
bitOr(x,y) (x|y) using only ~ and & 1 8
copyLSB(x) Word with all bits set to LSB of x 2 5
isEqual(x,y) (x==y) 2 5
reverseByte(x) Reverse the bytes of x 3 25
evenBits(void) Even-numbered bits set to 1 2 8
bitParity(x) 1 if x has odd number of 1's and 0 otherwise 4 20
leastBitPos(x) Mask with position of least significant 1 bit marked. 4 30

Table 1: Bit-Level Manipulation Functions.

Table 1 describes a set of functions that manipulate and test sets of bits. The "Rating" field gives the difficulty rating (the number of points) for the puzzle, and the "Max ops" field gives the maximum number of operators you are allowed to use to implement each function.

  • Functions bitAnd() and bitOr() should duplicate the behavior of the bit operations & and |, respectively. In bitAnd() you may only use the operations | and ~, while in bitOr() you may only use the operations & and ~.
  • Function copyLSB() generates a word in which every bit is set to the same value as the least significant bit of x.
  • Function isEqual() compares x to y. As with all predicate operations, it should return 1 if the tested condition holds and 0 otherwise.
  • Function reverseByte() generates a word by reversing the order of the bytes of x.
  • Function evenBits() generates a word in which the even-numbered bits are set to 1.
  • Function bitParity() returns 1 if its argument contains an odd number of 1's, and 0 otherwise.
  • Function leastBitPos() returns a mask that marks the position of the least significant 1 bit within x with a 1. All other positions of the mask should be 0.

Part II: Two's Complement Arithmetic

Name Description Rating Max Ops
tmin(void) Smallest two's complement integer 1 4
negate(x) -x 2 5
fitsBits(x,n) x can be represented with n bits 2 15
addOK(x,y) Can compute x+y without overflow 3 20
isLessOrEqual(x,y) x <= y 3 24
isNonZero(x) x!=0 without using ! or & 4 10
sm2tc(x) Convert sign-magnitude to two's complement 4 15
Table 2: Arithmetic Functions

Table 2 describes a set of functions that make use of the two's complement representation of integers:

  • Function tmin() returns the smallest integer.
  • Function fitsBits() determines whether argument x could be represented as an n-bit, two's complement number.
  • Function addOK() determines whether argument y can be added to argument y without overflow.
  • Function isLessOrEqual() determines whether x is less than or equal to y.
  • Function isNonZero() determines whether x != 0. To make things more interesting, you may not use the operation ! for this problem.
  • Function sm2tc() converts a number from sign-magnitude format to two's complement format. That is, the high order bit of x is a sign bit s, while the remaining bits denote a nonnegative magnitude m. The function should then return the two's complement representation of (-1)s*m.

Advice

You are welcome to do your code development using any system or compiler you choose. Note, that the version you turn in must compile and run correctly using our class machines. If it doesn't compile, we can't grade it.

The dlc program, a modified version of an ANSI C compiler, will be used to check your programs for compliance with the coding style rules. You can also use it to measure the operator counts of your functions. You can run these tests by executing the command:

./dlc -e bits.c

Check the file README for documentation on running the btest program. You'll find it helpful to work through the functions one at a time, testing each one as you go. You can use the -f flag to instruct btest to test only a single function, e.g., ./btest -f isPositive

Hand In Instructions

  • Make sure you have included your identifying information in your file bits.c.
  • Remove any extraneous print statements.
  • Create a team name of the form:
    • "ID" where ID is your Andrew ID, if you are working alone, or
    • "ID1+ID2" where ID1 is the Andrew ID of the first team member and ID2 is the Andrew ID of the second team member.
  • This should be the same as the team name you entered in the structure in bits.c.
  • To handin your bits.c file, type:
    make handin TEAM=teamname

    where teamname is the team name described above.

  • After the handin, if you discover a mistake and want to submit a revised copy, type
    make handin TEAM=teamname VERSION=2

    Keep incrementing the version number with each submission.

  • You can verify your handin by looking in
    /afs/cs.cmu.edu/academic/class/15213-s02/L1/handin

    You have list and insert permissions in this directory, but no read or write permissions.