CS 105

Puzzles: Bit Manipulation

The following table describes a set of functions that manipulate and test sets of bits. The “Rating" field gives the difficulty rating (the number of points) for the puzzle, and the “Max Ops” field gives the maximum number of operators you are allowed to use to implement each function. See the notes below as well as comments in bits.c for more details on the desired behavior of the functions.

Name Description Rating Max Ops
bitXor(x,y) ^ using only & and ~ 1 14
isNotEqual(x,y) x != y? 2 6
getByte(x,n) Extract byte n from x 2 6
copyLSB(x) Set all bits to least significant bit of x 2 5
logicalShift(x,n) Logical right shift x by n 3 20
bitCount(x) Count number of 1's in x 4 40
bang(x) Compute !x without using ! operator 4 12
leastBitPos(x) Mark least significant 1 bit 2 6

Bit-Level Manipulation Functions

  • bitXor should duplicate the behavior of the bit operation ^, using only the operations & and ~.

  • isNotEqual compares x to y for inequality. As with all predicate operations, it should return 1 if the tested condition holds and 0 otherwise.

  • getByte extracts a byte from a word. The bytes within a word are ordered from 0 (least significant) to 3 (most significant).

  • copyLSB replicates a copy of the least significant bit in all 32 bits of the result.

  • logicalShift performs logical right shifts. You may assume the shift amount \( n \) satisfies \( 0 \leq n \leq 31 \).

  • bitCount returns a count of the number of 1's in the argument.

  • bang computes logical negation without using the ! operator.

  • leastBitPos generates a mask consisting of a single bit marking the position of the least significant one bit in the argument. If the argument equals 0, it returns 0.

Testing Your Solutions

You can use the provided btest program to test your solutions as you work on them. Use the make command to build the btest program after each change to your bits.c file, and then run ./btest to see which tests pass and which fail.

The btest program also supports testing individual functions, as described in the Check Your Submission section.

You can also check that your solutions follow the coding rules using the dlc tool. Run ./dlc bits.c, and it will print out any violations of the coding rules.

(There are still some functions left to write, which we'll get to in the next parts of the lab instructions.)

To Complete This Part of the Assignment

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)