# 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 `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 the`zebra()`

function which returns the`n`

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 the`n`

th 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 `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.