Lab 1: Manipulating Bits Using C

Overview

Learning Objectives:

• Gain familiarity with data representations at the level of bits.
• Gain familiarity with pointers and pointer arithmetic.

Code for this lab

Get the code you need via one of these methods:

• Browser (click to download): lab1.tar
• Terminal: wget https://courses.cs.washington.edu/courses/cse351/18sp/labs/lab1.tar

Then extract the code into a directory with multiple files by running this terminal command from the directory containing the file you downloaded:

tar xf lab1.tar

Explanation of the tar program: tar is a file archive utility; the xf options mean to extract the file given as an argument. This should generate a directory next to lab1.tar called lab1 that contains a number of files described below.

Lab Instructions

bits.c and pointer.c contain skeletons for the programming puzzles, along with a comment for each function that describes exactly what the function must do and what restrictions there are on its implementation. Your assignment is to complete each function skeleton using:

• only straightline code (i.e., no loops or conditionals)
• a limited number of C arithmetic and logical operators
• no constants larger than 8 bits (i.e., 0–255 inclusive)
• as many (, ), and = as you need

The intent of the restrictions is to require you to think about the data as bits. Because of the restrictions, your solutions won't be the most efficient way to accomplish the function's goal, but the process of working out the solution should make the notion of data as bits completely clear.

Similarly, you will start working with basic pointers and use them to compute the size of different data items in memory and to modify the contents of an array.

The Bit Puzzles

This section describes the puzzles that you will be solving in bits.c. More complete (and definitive, should there be any inconsistencies) documentation is found in the bits.c file itself.

Bit Manipulations

The table below describes a set of functions that manipulate and test sets of bits. The Rating column gives the difficulty rating (the number of points) for each puzzle and the Description column states the desired output for each puzzle along with the constraints. 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

The following table 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.

Checking Your Work

We have included the following tools to help you check the correctness of your work in bits.c.

• We have included a print_binary function, which takes an integer and outputs its binary representation. This can be useful in debugging your code, but its use is optional and all calls to the function should be commented out in your final submission. See this video for usage examples.

• btest is a program that checks the functional correctness of the code in bits.c. To build and use it, type the following two commands:

  $ make
  $ ./btest

  Notice that you must rebuild btest each time you modify your bits.c file. (You rebuild it 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 bitXor

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

  $ ./btest -f bitXor -1 7 -2 0xf

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

  We may test your solution on inputs that btest does not check by default and we will check to see that your solutions follow the coding rules.

• dlc 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

  Note: dlc will always output the following warning, which can be ignored:

  /usr/include/stdc-predef.h:1: Warning: Non-includable file <command-line> included from includable file /usr/include/stdc-predef.h.

  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.
   

Advice

• Start early on bits.c!
• Puzzle over the problems yourself, it is much more rewarding to find the solution yourself than stumble upon someone else's solution.
• If you get stuck on a problem, move on. You may find you suddenly realize the solution the next day.
• There is partial credit if you do not quite meet the operator limit, but often times working with a suboptimal solution will allow you to see how to improve it.
• Do NOT include the <stdio.h> header file in bits.c, as it confuses dlc and results in some non-intuitive error messages. You will still be able to use printf for debugging without including the <stdio.h> header, although gcc will print a warning that you can ignore.
• You can use gdb (GNU debugger) on your code. See this transcript for an example.

• The dlc program enforces a stricter form of C declarations than is the case for C++ or that is enforced by gcc. In particular, in a block (what you enclose in curly braces) all your variable declarations must appear before any statement that is not a declaration. For example, dlc 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;
  }

Using Pointers

This section describes the functions you will be completing in pointer.c that is also in the lab1 folder you downloaded. Refer to pointer.c itself for more complete details. You are permitted to use casts for these functions.

Pointer Arithmetic

The first three functions in pointer.c ask you to compute the size (in bytes) of various data elements (ints, doubles, and pointers). You will accomplish this by noting that arrays of these data elements allocate contiguous space in memory so that one element follows the next.

Manipulating Data Using Pointers

The changeValue function in pointer.c asks you to change the value of an element of an array using only the starting address of the array. You will add the appropriate value to the pointer to create a new pointer to the data element to be modified.You are not permitted to use [] syntax to access or change elements in the array anywhere in the pointer.c file.

Pointers and Address Ranges

The last two functions in pointer.c ask you to determine whether pointers fall within certain address ranges, defined by aligned memory blocks or arrays.

Checking your work

We have included the following tools to help you check the correctness of your work in pointer.c:

• ptest.c is a test harness for pointer.c. You can test your solutions like this:

  $ make ptest
  $ ./ptest

  This only checks if your solutions return the expected result. We may test your solution on inputs that ptest does not check by default and we will review your solutions to ensure they meet the restrictions of the assignment.

• dlc.py is a Python script that will check for compliance with the coding rules (note that dlc does not work with pointer.c). The usage is:

  $ python dlc.py

Reflection

Make sure your answers to these questions are included in the file lab1reflect.txt!

Assuming that x = 351, as in the original code of lab0.c:

1. Find a positive value of y < x such that x & y = 0. Answer in hex.  [1 pt]
2. Find a negative value of y such that x ^ y = -1. Answer in decimal.  [1 pt]
3. Consider the following two statements:
   • y = -1;
   • y = 0xFFFFFFFF;
   Is there a difference between using these two statements in your code? Explain. If there is a difference, make sure to provide an example.  [1 pt]

Submitting Your Work

You will submit your completed files via Canvas (link is at the top of this page) in the following stages:

Preliminary:   By the preliminary deadline, we expect you to have 3 functions of your choice in bits.c completed and passing all tests (including using the proper number of operations). The purpose of this deadline is help you get started early on the assignment and it will be worth a small-ish number of points (no more than 10% of the total points for lab 1). Files submitted that contain at least 3 functions passing the spec will receive full credit for this stage. We will ignore all non-functioning/incomplete functions in the file, although please do ensure that the file will compile and run before submitting. We strongly encourage you to have more of the assignment done — 3 functions is just the minimum.

Final:   Submit your completed bits.c, pointer.c, and lab1reflect.txt files (three separate files). This will be a complete re-grade of the entire bits.c file — you are welcome to change anything you submitted for the preliminary submission.