# Lab 1: Manipulating Bits Using C

Assigned Monday, April 2 Monday, April 9 At least three functions in bits.c implemented and passing all tests (including proper number of operations) Friday, April 13 packaged in: lab1.tar 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:

• Gain familiarity with data representations at the level of bits.
• Gain familiarity with pointers and pointer arithmetic.
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:

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

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

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

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