Collaboration

For assignments in CIS 2400, you will complete each of them on your own 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 Docker Setup. We recommend you try and figure this out ASAP.

Once you have the environment set up, you should boot it up, and download the appropriate tar file and compiler based on your machine. To download them, you should open the terminal and use the provided command:

• This is for Windows, Linux and non M1/M2 Mac users:

curl -o binary_puzzles.tar https://www.seas.upenn.edu/~cis2400/current/projects/code/binary_puzzles_x86.tar

and this for the x86 compiler:

apt-get install -y gcc-multilib

• This is for M1 and M2 Mac users:

curl -o binary_puzzles.tar https://www.seas.upenn.edu/~cis2400/current/projects/code/binary_puzzles_arm.tar

and this for the arm compiler:

apt-get install -y gcc

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:

tar -xvf binary_puzzles.tar

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

Instructions

Once you have followed the setup instructions, there should be a folder called binary_puzzles 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 17 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.

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.

You may find it useful to review the text editors and terminal as decribed in the docker setup and the previous homework. We also have the bash reference that may be useful.

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

For these puzzles, you will typically 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. Some puzzles may give you a char as a parameter. Remember that a char is an 8-bit integer type, that can represent an ascii character.

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.

Compiling and Testing

To test your code locally, you will first need to navigate in the terminal 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. 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 negate
• 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

printf

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.

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.

• The first couple puzzles (difficulty 1 or 2) are somewhat foundational. They should help familiarize some concepts that will be important for later puzzles. You should be sure to do these before moving on

• If you are stuck, it may help to get something that uses too many operators but still works. Often times working with a suboptimal solution will allow you to see how to improve/simplify it.

• If you are stuck, don’t forget that you can come to Office Hours for help!

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

• 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