Description

5/5 - (2 votes)

The idea is to familiarize yourself with bit-level integer representation by solving a set of programming puzzles.

To start, copy datalab.tgz from CCLE to a (protected) directory on a GNU/Linux machine in which you plan to do your work. Extract its files by running the following shell command:

tar xf datalab.tgz

This will cause a number of files to be unpacked in the directory. 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 ‘README’ file contains additional documentation about ‘btest’. Use the command ‘make btest’ to generate the test code and run it with the command ‘./btest’. The file ‘dlc’ is a compiler

binary that you can use to check your solutions for compliance with the coding rules. The remaining files are used to build ‘btest’. Looking at the file ‘bits.c’, you will notice a C structure ‘studentID’ into which you should insert the requested identifying information about yourself. Do this immediately so that you do not forget.

The ‘bits.c’ file contains a skeleton for each of the 8 programming puzzles. Your assignment is to complete each function skeleton using only straightline code for the integer puzzles (i.e., no loops or con-ditionals) 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. Also, you are not allowed to use any constants longer than 8 bits. See the comments in ‘bits.c’ for detailed rules and a discussion of the desired coding style.

 

The Puzzles
Tables 1 and 2 describe a set of functions that manipulate and test sets of bits and twos complement arithmetic. The “Rating” field gives the difficulty rating for the puzzle, and the “Max Ops” field gives
the maximum number of operators you are allowed to use to implement each function. See the comments in bits.c for more details on the desired behavior of the functions. You may also refer to the test functions in ‘tests.c’. These are used as reference functions to express the correct behavior of your functions, although they don’t satisfy the coding rules for your functions.

Bit Manipulations

Table 1 describes a set of functions that manipulate and test sets of bits. Refer to the comments in ‘bits.c’ and the reference versions in ‘tests.c’ for more information.

Table 1: Bit-Level Manipulation Functions.

Name Rating Max Ops Description
howManyBits(x) 4 90 Minimum bits for 2s complement.
rotateRight(x) 3 25 Rotate x to the right by n.
allOddBits(x) 2 12 Check if all odd-numbered bits are 1.
bitXor(x, y) 1 14 Implement x^y using only ~ and &.

 

Two’s Complement Arithmetic

Table 2 describes a set of functions that make use of the two’s complement representation of integers. Again, refer to the comments in bits.c and the reference versions in tests.c for more information.

Table 2: Arithmetic Functions

Name Rating Max Ops Description

sm2tc(x) 4 15 Convert sign-magnitude to two’s complement.

isNonNegative(x) 3 6 Return 1 if x >= 0, 0 otherwise.

divpwr2(x, n) 2 15 Compute x/(2**n).

isTmin(x) 1 10 Check if x is the minimum integer.

 

Evaluation

Your score will be computed out of a maximum of 36 points based on the following distribution:
20 Correctness points.

16 Performance points.

Correctness points. The 8 puzzles you must solve have been given a difficulty rating between 1 and 4. We will evaluate your functions using the btest program, which is described in the next section. You will get full credit for a puzzle if it passes all of the tests performed by btest.

Performance points. 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. This limit is very generous and is designed only to catch egregiously inefficient solutions. You will receive two points for each correct function that satisfies the operator limit.

In order to get a perfect score on this assignment, you need to get 30 points. There are also 6 bonus points if you do all the problems right.

 

Handin Instructions

* Make sure it compiles (NO WARNINGS), passes the dlc test, and passes the btest tests on the class machine (lnxsrv.seas.ucla.edu).
* Make sure you have included your identifying information in your

file ‘bits.c’.

* Remove any extraneous print statements.

* Submit your ‘bits.c’ file to CCLE where indicated under Lab 1.

 

Advice

You are welcome to develop your solution using any system or compiler you choose. However, make sure that the version you turn in can compile and run correctly on our class machine (lnxsrv.seas.ucla.edu). If it does not compile, we cannot grade it.

The dlc program is a modified version of an ANSI C compiler that you can use to check for compliance with the coding rules for each
puzzle. The typical usage is:

./dlc bits.c

Type ‘./dlc -help’ for a list of command line options. The ‘README’ file is also helpful. Some notes on ‘dlc’:

* The ‘dlc’ program runs silently unless it detects a problem.

* Do NOT include ‘<stdio.h>’ in your ‘bits.c’ file, because it confuses ‘dlc’ and results in some non-intuitive error messages.

Check the ‘README’ file for documentation on running the ‘btest’ program. You will 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 isTmin’.