Lab 1: Manipulating Bits¹

• Assigned: Monday, April 11
• Check-in Post: Before 9pm Friday, April 15 (check-in forum)
• Due: 9pm Wednesday, April 20
• Collaboration: This is an individual assignment
• Handout:
  • Linux starter project
  • MacOS starter project
• Submit: Upload bits.c to Lab 1
• Reference:
  • Integer Representation
  • Integer Arithmetic
  • Bitwise and Boolean operators (especially the practice problems)

Introduction

The purpose of this assignment is to become more familiar with bit-level representations of integers and how to use bitwise operators. 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

To test your solution for this lab on your own computer, you will need to have Perl installed. Fortunately, Perl is included by default on both Linux and MacOS.

  wget http://cs.carleton.edu/faculty/awb/cs208/s22/handouts/lab1-handout.tar

  wget http://cs.carleton.edu/faculty/awb/cs208/s22/handouts/lab1-handout-mac.tar

  ./dlc: cannot execute binary file

  tar xvf lab1-handout.tar

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.

 ! ~ & ^ | + << >>

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

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

The table below lists the puzzles in rough order of difficulty from easiest to hardest. The Rating field gives number of points the puzzle is worth, 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.

Testing

  make test

to run the complete autograding of your work. Details on the specific autograding components are below.

btest

  make
  ./btest

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

  ./btest -f bitXor

  ./btest -f bitXor -1 4 -2 5

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

dlc

  ./dlc bits.c

  ./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.

driver.pl

  perl driver.pl

Implementation Advice

• Don’t include the <stdio.h> header file in your bits.c file, as it confuses dlc 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, although gcc will print a warning that you can ignore.

• The dlc program enforces a stricter and older form of C declarations than gcc enforces. In particular, any declaration must appear in a block (what you enclose in curly braces) before any statement that is not a declaration. For example, it will complain about the following code:

  int foo(int x)
  {
    int a = x;
    a *= 3;     /* Statement that is not a declaration */
    int b = a;  /* ERROR: Declaration not allowed here */
  }

  Instead, you must declare all your variables first, like this:

  int foo(int x) {
    int a = x;
    int b;
    a *= 3;
    b = a;
    return b+2
  }

• The dlc checker does not accept the 0b prefix for numbers in binary notation (e.g., 0b11110000). Do not use it. Use decimal (e.g., 240) or hexadecimal (0xf0) notation only. The included ishow tool lets you display integer representations and conversions. It takes hex or decimal input.

  ./ishow 0x27
  
  Hex = 0x00000027, Signed = 39,    Unsigned = 39

Grading

Your program will be evaluated out of 60 points using the following distribution.

• 39 Correctness points.
• 18 Performance points.
• 3 Check-in post points.

Correctness points

The puzzles you must solve have been given a rating of 1, 2, 5, or 6, such that their weighted sum totals to 39. 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. Partial credit may be awarded for solutions that do not pass the tests.

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 2 points for each correct function that satisfies the operator limit.

The “Beat the Prof” Contest

For fun, I am offering an optional “Beat the Prof” contest that allows you to compete with other students and the nefarious Mr. Dr. The Professor to develop the most efficient puzzles. The goal is to solve each Data Lab puzzle using the fewest number of operators. See if you can match or beat Mr. Dr. The Professor’s operator count for each puzzle!

  ./driver.pl -u "Your Nickname"

  http://awb66333.mathcs.carleton.edu:8080

You will need to be on campus or connected to the Carleton VPN to submit an entry and view the scoreboard.