Data Puzzles

Introduction

The purpose of this assignment is to become more familiar with bit-level representations of integers and floating point numbers. 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

This is an individual project. Clarifications and corrections will be posted on the class website. You will submit your solution via Gradescope.

Handout Instructions

Start by downloading the starter code to a directory on a Linux machine in which you plan to do your work. Here are the commands that will do this for you:

cd cs224
wget --no-check-certificate https://cs224.cs.vassar.edu/assignments/data_puzzles.tar
tar -xvf data_puzzles.tar  
rm data_puzzles.tar
cd data_puzzles

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 bits.c file contains a skeleton for each of the programming puzzles. Your assignment is to complete each function skeleton using only straightline code for the integer puzzles (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. Also, you are not allowed to use any constants longer than 8 bits.

Coding Rules

Please read the following instructions carefully. You will provide your solution to this assignment by editing the collection of functions in this source file. There are two types of problems, integer and floating-point. They each have slightly different rules.

Integer Coding Rules

Replace the return statement in each function with one or more lines of C code that implements the function. Your code must conform to the following style:

  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

Each “Expr” is an expression using only the following:

  1. Integer constants 0 through 255 (0xFF), inclusive. You are not allowed to use large constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>

Some of the problems restrict the set of allowed operators even further. Each “Expr” may consist of multiple operators. You are not restricted to one operator per line.

You are expressly forbidden to:

  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int. This implies that you cannot use arrays, structs, or unions.

You may assume that your machine:

  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting if the shift amount is less than 0 or greater than 31.

Examples of Acceptable Coding Style

  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }

  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }

Floating Point Coding Rules

For the problems that require you to implement floating-point operations, the coding rules are less strict. You are allowed to use looping and conditional control. You are allowed to use both ints and unsigneds. You can use arbitrary integer and unsigned constants. You can use any arithmetic, logical, or comparison operations on int or unsigned data.

You are expressly forbidden to:

  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned. This means that you cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.

Notes

  1. Use the btest test harness to check your functions for correctness. First, build your solution by typing make in the data-puzzles directory. Then you can type ./btest to test your solution.
  2. Use the dlc (data lab checker) compiler to check the legality of your solutions. To compile your code and run the checker you can type ./driver from the Linux prompt in your data-puzzles directory.
  3. Each function has a maximum number of operations (integer, logical, or comparison) that you are allowed to use for your implementation of the function. The max operator count is checked by dlc. Note that assignment (=) is not counted; you may use as many of these as you want without penalty.
  4. The maximum number of ops for each function is given in the header comment for each function.
  5. To avoid grading surprises, run ./driver.pl to test for both correctness and the validity of your solution.

The Puzzles

This section describes the puzzles that you will be solving in bits.c.

Bit Manipulations

A number of the puzzles manipulate and test sets of bits. Each puzzle has a “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.

Two’s Complement Arithmetic

Several of the functions make use of the two’s complement representation of integers. Like the bit manipulation functions, they each have a difficulty rating and a maximum number of allowed operations. Again, refer to the comments in bits.c and the reference versions in tests.c for more information.

Boolean Algebra

The following Boolean Algebra identities may be helpful to you in this assignment.

A | 0 == A
A & 1 == A
A | A == A
A & A == A

A | ~A == 1
1 | A == 1    # This operation sets a bit to 1

A & ~A == 0
0 & A == 0   # This operation clears a bit to 0

A ^ A == 0
1 ^ A == ~A  # This operation flips a bit 

A | B == B | A
A & B == B & A

A | (B | C) == (A | B) | C
A & (B & C) == (A & B) & C

Distributive Law:
A & (B | C) == A & B | A & C
A | B & C == (A | B) & (A | C)

De Morgan's Theorem:
~(A & B) == ~A | ~B
~(A | B) == ~A & ~B

Evaluation

Your score will be based on correctness and validity as determined by running ./driver.pl.

Correctness points.: The puzzles have been given a difficulty rating. Lower ratings (i.e., 1) are generally easier than higher ratings, so you may want to start with the lower rated puzzles first. Points are awarded depending on the rating of the puzzle.

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 for each function. 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.

Style points. Finally, we’ve reserved 20 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.

You can test your functions by first typing make and then typing ./btest. You will get credit for a puzzle if it passes all of the tests performed by btest. For each puzzle 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 must only use the operators allowed by the puzzle and arrive at a solution within the maximum number of operators allowed. To check if you are within these bounds, use the dlc program (by typing ./driver.pl). To get full credit for the puzzle it must pass both the btest and dlc programs. The following command will run both tests for you and show you the total of your correctness and performance scores.

./driver.pl

Checking your work

We have included some autograding tools in the handout directory – btest and dlc to help you check the correctness of your work.

btest: This program checks the functional correctness of the functions in bits.c. To build and run it, type the following command:

make
./btest

Notice that you must rebuild btest each time you modify your bits.c file by typing make.

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:

./btest -f tmax

You can feed it specific function arguments using the option flags -1, -2, and -3:

./btest -f isZero -1 25

Check the file README for documentation on running the btest program.

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

./dlc bits.c

The program runs silently unless it detects a problem, such as an illegal operator, too many operators, or non-straightline code in the integer puzzles. Running with the -e switch:

./dlc -e bits.c

causes dlc to print counts of the number of operators used by each function. Type ./dlc -help for a list of command line options. To run this checker automatically you can type:

./driver.pl

Important: You must test your solutions with both btest and dlc. To get full credit for a puzzle, it must pass both of these programs.

If you have any dlc errors, you need to fix them. dlc is picky about where you can declare your variables. You must declare them at the top of your function before any statements. If you get a dlc parse error and you don’t see any errors in your code, try declaring your variables at the top of your function to fix it.

Debugging your code with printf

It may be helpful to print out the value of some of your variables if you are trying to figure out why something is going wrong. You can use the printf function to do that.

Here’s an example of now to use printf to print out an integer variable:

int x = 42;
printf("x has the value of %d\n", x);

If you wanted to print out the value of your integer as a hexadecimal number, you can use the %x format specifier instead of %d.

When you add the printf to one of your c functions, you might get a warning when you build your program. Do not include the <stdio.h> header file in your bits.c file to fix the warning. Including any header files confuses the dlc program and results in some non-intuitive error messages. You will still be able to use printf in your bits.c file for debugging without including the <stdio.h> header file, just ignore the warning you get.

Once you are finished debugging your function, remove the printf from your code.

Submission Instructions

To submit your work, upload your bits.c file for Assignment 1 on gradescope.