Collaboration

For assignments in CS 2400, you will complete each of them on your own or solo. However, you may discuss high-level ideas with other students, but any viewing, sharing, copying, or dictating of code is forbidden. If you are worried about whether something violates academic integrity, please post on Ed or contact the instructor.

Setup

If you haven’t already, you need to follow the VMWare setup. We recommend you try and figure this out ASAP.

Once you have the VM setup, you should boot it up, and download the appropriate tar file based on your machine. To download them, you should open the terminal (which should be an application on the right hand side of the desktop) and use the provided command:

This is for Windows, Linux and non M1/M2 Mac users: wget https://www.seas.upenn.edu/~cis2400/22fa/projects/code/hw1_x86.tar
This is for M1 and M2 Mac users: wget https://www.seas.upenn.edu/~cis2400/22fa/projects/code/hw1_arm.tar

After downloading the tar file, you should be able to type in the command “ls” in the terminal, or use the file explorer to see the download tar file. Once you confirm that the file is downloaded, run the following command to decompress the files:

For Windows, Linux and non M1/M2 Mac users: tar -xvf hw1_x86.tar
For M1 and M2 Mac users: tar -xvf hw1_arm.tar

You should now have a directory called hw1 that contains the files necessary for this assignment.

Instructions

Once you have followed the setup instructions, there should be a folder called hw01 that contains the file for this assignment. The only file you need to modify for this assignment is bits.c. The bits.c is a C programming file, and it contains the skeleton for 11 binary puzzles.

Each of these puzzles will be contained in a C function that you will have to complete. This means that you will have to write a little bit of C code, but if you have programmed in java and are familiar with C binary operators, that should be enough (there is also a refresher on some of these operators here. These puzzles will each have their own restrictions on the operators you are allowed to use, some general restrictions are also outlined below for each “type” of question.

C doesn’t provide variables with a default initial value like Java does. When you declare a new variable be sure that you assign it a value.

Complete documentation on what kind of code is allowed and disallowed can be found at the beginning of the bits.c file. We will also give an overview of the restrictions on each type of puzzle below.

There are also provided ways to make sure your solutions behave correctly and follow the provided restrictions. You can read more on how to test in the Compiling and Testing section below.

It may also be helpful for you to write print statements for debugging purposes. We have information on how to print in C in the printf section below.

Binary Puzzles

Task 1. Read over and complete the binary puzzles listed below. Write your solution as code in bits.c.

For these puzzles, you will be given an int variable (which is a signed 2C type) and you will have to return the appropriate value for every possible integer input. For some of these puzzles, while the input is a 2C integer, you should think of the input as being a sequence of 32-bits and not so much as a number.

The code you write for each of these puzzles must follow certain rules, you can find these rules at the top of bits.c but here is an overview on them:

You can only write “straightline” code for these puzzles (no loops, conditionals or function calls in your final solution)
You may not use any macros or casting.
no constants outside the range of 8 bits (i.e. 0 - 255 inclusive)
no unsigned data types, structs, arrays, floating point types, or unions
a limited amount of C arithmetic operators and logical operators, with some operators being banned from certain problems
You are allowed to declare new int variables and use any amount of parenthesis and assignment operators. These are the operators “(“, “)” and “=”.

These restrictions are here so that you can get comfortable with the bit-wise operators and thinking with bits.

Below we have a table listing out the each of these puzzles, their somewhat subjective difficulty rating and a description of the problem. You will have to implement these puzzles in bits.c and each of the functions will have a comment before them further explaining the problem and restrictions.

There are 3 puzzles that have a rating of 4, you will only need to complete 2 of these 3 puzzles to get full credit for this section. Completing all three “4-rating” puzzles will get you a small amount of extra credit.

Function Name	Rating	Description
bitAnd	1	x&y using only ~ and \|
bitNor	1	~(x\|y) using only ~ and &
negate	1	return -x
getByte	2	Extract byte n from word x
byteSwap	3	swaps the nth byte and the mth byte
isEqual	3	return 1 if x == y, and 0 otherwise
fitsBits	4	return 1 if x can be represented as an n-bit 2C integer
addOK	4	Determine if can compute x+y without overflow
absVal	4	returns the absolute value of x

Float Puzzles

For the floating-point puzzles, you will implement some common single-precision floating-point operations. To allow for us to perform operations more easily, the functions will not be passed parameters of type float and instead be passed in as type unsigned (unsigned 32-bit integer) containing the same bits as if it were of type float. Your code should perform the bit manipulations that implement the specified floating point operations by operating on the unsigned inputs.

The floating point puzzles have slightly different restrictions than the other puzzles.

You are allowed to use standard control structures (conditionals, loops)
You may use both int and unsigned data types
You may use any arbitrary unsigned and integer constants

However, some rules are still the same:

You still have a limited amount of C arithmetic operators and logical operators, with some operators being banned from certain problems
You may not call any functions or use any macros or casting.
You are still allowed to use any amount of parenthesis and assignment operators. These are the operators “(“, “)” and “=”.
You may not use any unions, structs, arrays, and most importantly, no floating point data types, operations or constants

There is also a program provided called fshow that you may find useful to understand the structure of floating point numbers. Read the section on Compiling and Testing below for more information.

There are 2 puzzles under this category. Below we have a table listing out the each of these puzzles, their somewhat subjective difficulty rating and a description of the problem. You will have to implement each of these in bits.c and each of the functions will have a comment before them further explaining the problem and restrictions.

Function Name	Rating	Description
floatAbsVal	2	Compute the absolute value of f for floating point argument f.
floatIsEqual	3	Compute f == g for floating point arguments f and g.

Navigating the Terminal

You will have to use the terminal a little bit in this HW. We are trying to introduce you to this a little bit now so it is less shocking during other (probably more time-consuming) assignments.

At a high level, you can compare the terminal to a text version of File Explorer on Windows or Finder on Mac. Just as with File Explorer or Finder, you are always in a directory (also called a folder) and can move beetween folders.

When you open the terminal you should see something like:

init_terminal

This “~” indicates that you are in the home directory, which is called “~”

To explore the files available to you, there are various commands you can input into the terminal:

ls is short for “list” and provides you a way to list out the contents of the directory you are currently in.
cd <directory_name> is short for “change directory” and allows us to navigate into the specified directory. If we were to run cd .. you can go “up a level” in the file system, in other words, this brings you to the parent directory (the direcetory that the current directory is contained in)

Lets use walk through a step-by-step process of how we can navigate to the directory that our HW1 files are located in. You will need to be in this directory to test your submission locally. This step by step process assumes you have completed the setup instructions above to download and unpack the HW1 files.

Starting from a fresh treminal session, if we run ls right now, you should see something like the image below. In this image, we can see a file called hw1_x86.tar or hw1_arm.tar and several directories (including a directory called hw1).

From here, if we were to run cd hw1 we can enter the directory that contains the files necessary for HW1.
We can then again run ls to see the contents of the hw1 directory as shown below

ls_cd_ls

From here we can edit the files necessary with some sort of text editor (vim/emacs/nano/sublime/etc.), compile the assignment, and run tests.

Text Editors

To complete the homework, you will have to edit bits.c. To do this, you need to use some sort of text editor. We have sublime-text instaled on the CIS 2400 VM that you should be able to access on the right hand side of the desktop as shown below:

sublime_hover

From here, you should be able to select File > Open File, navigate to where the HW01 files are, and select to open bits.c. You should now be able to edit bits.c and complete the assignment.

There are also other options for text editors if you desire to use something else:

One group of text editors are those that are used in the terminal. The most commonly used one in the terminal are vim, emacs, and nano. Note that these can take a little time to learn, but are often more intimidating than they actually are. You are free to use these if you want, and Travis is able to answer questions about vim if you post to Ed.

Another option is installing or using some other graphical text editor. Common ones include: notepad, notepad++, atom, VS code, and many others. You should be able to install these into your VM safely, though we cannot garuntee that course staff will be able to answer questions about these editors.

Compiling and Testing

To test your code locally, you will first need to navigate in the terimal to where your bits.c file is. Once you are there, run the command make in the terminal. This command will compile your code and print any warnings/errors. We highly suggest you fix any errors and warnings except for the printf warning mentioned (below)[#printf]. **You will NEED to run this command again after each time you modify bits.c and want to test your code again.

Once you have run make there should be multiple programs you can now run to test your code:

btest: This program checks the functional correctness of the functions in bits.c. You MUST run the make command each time you modify bits.c. To run the code, type the following command into the terminal: ./btest 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. For example: ./btest -f bitAnd
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 causes dlc to print counts of the number of operators used by each function. Example usage with -e is: ./dlc -e bits.c
fshow: This program helps you understand the structure of floating point numbers. You can use fshow to see what an arbitrary bit pattern represents as a floating-point number:

$ ./fshow 0x2

Floating point value 2.802596929e-45
Bit Representation 0x00000002, sign = 0, exponent = 0x00, fraction = 0x000002
Denormalized.  +0.0000002384 X 2^(-126)

printf

While you may use printing for debugging, you MUST remove any print statements from your code before submitting. Otherwise, the tests may encounter some errors.

When compiling the code, it may complain the printf is not properly defined. You can ignore this error. You also should not try to #include<stdio.h> to get rid of this warning.

printf is a C function used for printing output when the program runs. This is comparable to System.out.println from Java. Since we haven’t covered C yet, here is some basics of using printf that should cover your printing needs for this assignment.

Assume we have an integer variable int a; defined somewhere in our code. If you wanted to print out the decimal value of a on a new line, you would write the line of code: printf("%d\n", a);.

We can make our print message have a little more context by modifying the string passed in to printf. An example of this would be: printf("The value of a is %d\n", a);.

If we want to print out the value of a in hexadecimal, we just need to replace the %d with %X. For example printf("%X\n", a);. Note that we cannot print a in binary just using a single call to printf. If you want the exact binary, we recommend you print the value in hexadecimal and convert hexadecimal to binary.

Operator Review

Since some of the C bit operators may be new to you, we are providing a table below that lists some of them alongside a description of them. For this table, assume that a and b are defined as ints.

Operator	Usage	Description
`!`	!a	The "bang" operator. If `a` is `0`, `!a` evaluates to `1` if `a` is non-zero, `!a` evalutes to `0`
`~`	~a	Performs a bit-wise "not" operation on `a`. Every bit that is a `1` in `a` becomes a `0` and vice-versa
`&`	a & b	Performs a bit-wise AND operation on the bits in `a` and `b`
`^`	a ^ b	Performs a bit-wise XOR operation on the bits in `a` and `b`
`\|`	a \| b	Performs a bit-wise OR operation on the bits in `a` and `b`
`+`	a + b	Performs addition on `a` and `b`
`<<`	a << b	Shifts the bits in `a` to the left `b`-times
`>>`	a >> b	Shifts the bits in `a` to the right `b`-times. If `a` is a signed type, then it is an arithmetic shift. If `a` is an unsigned type, it is a logical shift.

Advice and Misc Tips

C doesn’t provide variables with a default initial value like Java does. When you declare a new variable be sure that you assign it a value.
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.
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 form of C declarations than is the case for more recent versions of C. 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, the above code should be written like:

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

Submission

Please submit your completed bits.c to Gradescope