Bitwise Operations Exercises

To access the starter code for these exercises, use the following command:

git clone /afs/ir/class/archive/cs/cs107a/cs107a.1224/WWW/exercises/bitwise-operations

For solutions, see the _soln.c versions of the C files.

p1: zebra

Consider ints whose bit representation ends with alternating 1s and 0s. Here's an example:

0b0000_0000_0000_0010_1010_1010_1010_1010

Note that we've listed all 32 bits of the int, including leading zeroes.

Let's call such an int a "zebra number". The alternating pattern starts somewhere in the middle of the int, and continues on all the way to the LSB, which must be a 0.

We can uniquely identify zebra numbers by the number of 1s in their bit representation. Let's call the zebra number with n 1s the nth zebra number. (Assume n < 16.)

  1. In the file zebra.c, implement the zebra() function which returns the nth zebra number.
  2. Suppose we want to define zebra numbers differently so that instead of a "1010" pattern, zebra numbers have a "0101" pattern i.e. the LSB would be 1. Implement the zebra_alt() function which returns the nth zebra number given this alternate definition. Use the zebra() function you already wrote.

p2: battleship

Imagine a simplified version of the classic game Battleship. In this simplified version, we use a 8 by 8 grid gameboard, and all ships are 1 by 1.

If you're not familiar with Battleship, all you need to know is that before gameplay, each player places (in this version) 5 ships in 5 different spaces on their own gameboard.

Because there's exactly 64 spaces on a 8 by 8 grid gameboard, and because for each space, we only need to keep track of whether or not there's a ship there, we can efficiently represent a gameboard using a 64-bit long, where a 1 bit means a ship is present at that space, and a 0 bit means no ship is present.

In a long, we generally number the bits right-to-left, so the LSB is bit 0, and the MSB is bit 63. If we let the ith bit represent gameboard spaces in the following way:

56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7

then we get a convenient result: the space at the 0-indexed coordinate (row, col) is represented by bit 8*row + col.

Let's say you're given a long representing a gameboard. Inside the file battleship.c, implement the place_ship() function that returns a new gameboard where identical to the given gameboard except that a ship has been placed at the given coordinate by changing that bit to a 1, if it isn't already.

p3: color

Colors in software are generally represented by their red, green, blue, and alpha (transparency) components, each of which is a number between 0 and 255. This requires exactly 8 bits to represent a component's range, so we usually use a 32-bit unsigned int to hold all the bits to represent a color.

Suppose you're given an unsigned int representing a color where the order of the components within the unsigned int is BGRA (blue, green, red, alpha). In the color.c file, implement the bgra_to_rgb() function that takes in a BGRA unsigned int and produces a RGB unsigned int, where the most significant 8 bits are 0, the next 8 bits are the red component, then green, and then blue.

p4: binprint

printf has built-in functionailty to print in decimal and hex (%d and %x). It unfortunately doesn't let you print in binary. In the file binprint.c, implement the function binprint() which takes in an int and prints out all 32 bits on a single line, including leading zeroes.