Bitwise Operations Exercises
To access the starter code for these exercises, use the following command:
git clone /afs/ir/class/archive/cs/cs107a/cs107a.1226/WWW/exercises/bitwise-operations
For solutions, see the _soln.c
versions of the C files.
p1: zebra
Consider int
s 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 n
th zebra number.
(Assume n
< 16.)
- In the file
zebra.c
, implement thezebra()
function which returns then
th zebra number. - 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 then
th zebra number given this alternate definition. Consider using thezebra()
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 i
th 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.