Lab 3: Bit and Byte Manipulations in C

• Lab 3: Bit and Byte Manipulations in C
  • Acknowledgements
  • Overview
  • Background
• Useful code.
  • Bit Manipulation Puzzles
  • Two's Complement Puzzles
  • Test
  • Validation
  • Advice
  • Reflection

You might find it helpful to understand the helper function print_binary() as well as a few more bit tricks you might find helpful for this lab.ASK YOUR TA

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 the video link at the top of this page for usage examples.

Acknowledgements

This lab has been modified by Arrvindh Shriraman, Justin Tsia, and derived from CS:APP Textbook.

Overview

Learning Objectives:

• Gain familiarity with data representation at the level of bits.
• Gain practical knowledge of bit manipulation in C.

You will solve a series of programming "bit puzzles." 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.

Background

bits.c contains skeletons for the programming puzzles, along with a comment block 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 (you can also use shorthand versions of "legal" operators--ex. you can use ++ and += if + is legal)
• no constants larger than 8 bits (i.e., 0 - '255 inclusive)--however, you are allowed to combine constants to values greater than 255 or less than 0. e.g. 250 + 250 = 500, so long as the operator you're using to combine the constants is listed as "legal" at the top of the method you're writing
• 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.

Useful code.

These are small programs that you might useful for the task in hand.

• Week 2 shift 1
• Week 2 shift 2

Bit Manipulation Puzzles

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 Puzzles

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.

Test

We have included the following tools to help you check the correctness of your work:

• 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 the video link at the top of this page 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.

• The make command additionally produces two helper executables called ishow and fshow that can be used to view conversions between decimal values and bit representations for integers and floating point numbers, respectively. For more information about using them, see the end of the README file.

Validation

We have included a program to validate if you are following the rules specified in the comments.

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

• 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;
  }
  

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

• The dlc program will also complain about binary constants such as 0b10001000, so avoid using them.

Advice

• 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.
• Often times working with a suboptimal solution will allow you to see how to improve it.

Reflection

1. In your opinion, which restricted operator was the most difficult to reproduce? What was your solution and, more importantly, why does it work?

2. Consider the following function:

   int mystery(int x) {
     int mask = x >> 31;
     return (x ^ mask)
       + ~mask + 1L;
   }
   

   What does this function do? Describe explicitly what each of the three lines does and what the final result is.  [4 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.