Lab 1: Manipulating Bits Using C

Assigned Monday, April 2
Preliminary Due Date Monday, April 9 At least three functions in bits.c implemented and passing all tests (including proper number of operations)
Final Due Date Friday, April 13
Files packaged in: lab1.tar
Submissions Submit your completed bits.c and pointer.c via the Canvas assignments page (go to the Labs section, not the Homeworks section).

Overview

Learning Objectives:

You will solve a series of programming “puzzles.” The first part is about using bit manipulations. Many of these may seem artificial, but bit manipulations are very useful in cryptography, data encoding, implementing file formats (e.g., MP3), and certain job interviews. The second part is about basic pointer manipulations and pointer arithmetic. Pointers are a critical part of C and necessary for understanding assembly code (Lab 2-3) and memory allocation (Lab 5).

Code for this lab

Get the code you need via one of these methods:

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:

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.

Rating Function Name Description
1 bitAnd Compute x & y using only ~ and |

Hint: DeMorgan's Law

1 bitXor COmpute x ^ y using only ~ and &

Hint: DeMorgan's Law

1 thirdBits Return an int with every third bit (starting from the least significant bit) set to 1

Hint: keep in mind that the return value is 32 bits

2 getByte Extract the nth byte from int x

Hint: bytes are 8 bits

3 logicalShift Shift x to the right by n bits, using a logical shift

. You only have acces to arithmetic shifts in this function.

3 invert Invert (0s become 1s; 1s become 0s) n bits from position p to position p+n-1

Hint: use a bitmask

4 bang Compute !x without using the ! operator. Hint: Recall that 0 is false and anything else is true.

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.

Rating Function Name Description
2 sign Return 1 if positive, 0 if zero, and -1 if negative. Hint: shifting is the key.
3 fitsBits Return 1 if x can be represented as an n-bit, two's complement integer

Hint: -1 = ~0

3 addOK Return 1 if x+y can be computed without overflow. Hint: think about what happens to sign bits during addition.
Extra Credit:
4 isPower2 Return 1 if x is a power of 2, and 0 otherwise

Checking Your Work

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

Advice

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:

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