Deadline: EOD Tuesday, February 12th

- TSWBAT perform specific bit manipulations through compositions of bit operations.
- TSW become comfortable with using pointers while implementing algorithms in C.
- TSW identify potential issues with dynamic memory management.

For this exercise, you will complete `bit_ops.c`

by implementing the bit manipulation functions `get_bit`

, `set_bit`

, and `flip_bit`

(shown below). You may only use bitwise operations such as and (&), or (|), xor (^), not (~), left shifts («), and right shifts (»). You may not use any for/while loops or conditional statements.

```
// Return the nth bit of x.
// Assume 0 <= n <= 31
unsigned get_bit(unsigned x, unsigned n);
// Set the nth bit of the value of x to v.
// Assume 0 <= n <= 31, and v is 0 or 1
void set_bit(unsigned *x, unsigned n, unsigned v);
// Flip the nth bit of the value of x.
// Assume 0 <= n <= 31
void flip_bit(unsigned *x, unsigned n);
```

**ACTION ITEM**: Finish implementing `get_bit`

, `set_bit`

, and `flip_bit`

.

Once you complete these functions, you can compile and run your code using the following commands:

```
$ make bit_ops
$ ./bit_ops
```

This will print out the result of a few limited tests.

In this exercise, you will implement a `lfsr_calculate()`

function to compute the next iteration of a linear feedback shift register (LFSR). Applications that use LFSRs are: Digital TV, CDMA cellphones, Ethernet, USB 3.0, and more! This function will generate pseudo-random numbers using bitwise operators. For some more background, read the Wikipedia article on Linear feedback shift registers. In `lfsr.c`

, fill in the function `lfsr_calculate()`

so that it does the following:

- On each call to
`lfsr_calculate`

, you will shift the contents of the register 1 bit to the right. - This shift is neither a logical shift or an arithmetic shift. On the left side, you will shift in a single bit equal to the Exclusive Or (XOR) of the bits originally in position 0, 2, 3, and 5.
- The curved head-light shaped object is an XOR, which takes two inputs (a, b) and outputs a^b.
- If you implemented
`lfsr_calculate()`

correctly, it should output all 65535 positive 16-bit integers before cycling back to the starting number. - Note that the leftmost bit is the MSB and the rightmost bit is the LSB.

**ACTION ITEM**: Implement `lfsr_calculate()`

, compile `lfsr`

and run it. Verify that the output looks like the following:

```
$ make lfsr
$ ./lfsr
My number is: 1
My number is: 5185
My number is: 38801
My number is: 52819
My number is: 21116
My number is: 54726
My number is: 26552
My number is: 46916
My number is: 41728
My number is: 26004
My number is: 62850
My number is: 40625
My number is: 647
My number is: 12837
My number is: 7043
My number is: 26003
My number is: 35845
My number is: 61398
My number is: 42863
My number is: 57133
My number is: 59156
My number is: 13312
My number is: 16285
... etc etc ...
Got 65535 numbers before cycling!
Congratulations! It works!
```

Here’s one to help you in your interviews. In `ll_cycle.c`

, complete the function `ll_has_cycle()`

to implement the following algorithm for checking if a singly-linked list has a cycle.

- Start with two pointers at the head of the list. We’ll call the first one tortoise and the second one hare.
- Advance hare by two nodes. If this is not possible because of a null pointer, we have found the end of the list, and therefore the list is acyclic.
- Advance tortoise by one node. (A null pointer check is unnecessary. Why?)
- If tortoise and hare point to the same node, the list is cyclic. Otherwise, go back to step 2.
- After you have correctly implemented
`ll_has_cycle()`

, the program you get when you compile`ll_cycle.c`

will tell you that`ll_has_cycle()`

agrees with what the program expected it to output.

**ACTION ITEM**: Implement `ll_has_cycle()`

and execute the following commands to make sure that the provided tests pass.

```
$ make ll_cycle
$ ./ll_cycle
```

**Hint**: There are two common ways that students usually write this function. They differ in how they choose to encode the stopping criteria. If you do it one way, you’ll have to account for a special case in the beginning. If you do it another way, you’ll have some extra NULL checks, which is OK. *The previous 2 sentences are meant to urge you to not stress over cleanliness. If they don’t help you, just ignore them.* The point of this exercise is to make sure you know how to use pointers.

Here’s a Wikipedia article on the algorithm and why it works. Don’t worry about it if you don’t completely understand it. We won’t test you on this.

As a closing note, the story of the tortoise and the hare is always relevant, especially in CS61C. Writing your C programs slowly and steadily, using debugging programs like CGDB, is what will win you the race.

This exercise uses `vector.h`

, `vector-test.c`

, and `vector.c`

, where we provide you with a framework for implementing a variable-length array. This exercise is designed to help familiarize you with C structs and memory management in C.

**ACTION ITEM**: Explain why `bad_vector_new()`

and `also_bad_vector_new()`

are bad and fill in the functions `vector_new()`

, `vector_get()`

, `vector_delete()`

, and `vector_set()`

in `vector.c`

so that our test code `vector-test.c`

runs without any memory management errors.

Comments in the code describe how the functions should work. Look at the functions we’ve filled in to see how the data structures should be used. For consistency, *it is assumed that all entries in the vector are 0 unless set by the user. Keep this in mind as malloc() does not zero out the memory it allocates.*

For explaining why the two bad functions are incorrect, keep in mind that one of these functions will actually run correctly (assuming correctly modified `vector_new`

, `vector_set`

, etc.) but there may be other problems. **Hint**: think about memory usage.

**ACTION ITEM**: Test your implementation of `vector_new()`

, `vector_get()`

, `vector_delete()`

, and `vector_set()`

for both correctness and memory management (details below).

```
# 1) to check correctness
$ make vector-test
$ ./vector-test
# 2) to check memory management using Valgrind:
$ make vector-memcheck
```

All the `vector-memcheck`

rule does is run the following valgrind command on our executable. For a review, read through Exercise 4 in Lab 1. Explain to yourself what each of the flags mean.

```
$ valgrind --tool=memcheck --leak-check=full --track-origins=yes [OS SPECIFIC ARGS] ./<executable>
```

The last line in the valgrind output is the line that will indicate at a glance if things have gone wrong. Here’s a sample output from a buggy program:

```
==47132== ERROR SUMMARY: 1200039 errors from 24 contexts (suppressed: 18 from 18)
```

If your program has errors, you can scroll up in the command line output to view details for each one. For our purposes, you can safely ignore all output that refers to suppressed errors. In a leak-free program, your output will look like this:

```
==44144== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 18 from 18)
```

Again, any number of suppressed errors is fine; they do not affect us.

Feel free to also use CGDB or add `printf`

statements to `vector.c`

and `vector-test.c`

to debug your code.

Exercise 1:

- Show your TA/AI the output of running
`bit_ops`

.

Exercise 2:

- Show your TA/AI the output of running
`lfsr`

.

Exercise 3:

- Show your TA/AI the output of running
`ll_cycle`

.

Exercise 4:

- Explain to your TA/AI why
`bad_vector_new()`

and`also_bad_vector_new()`

are bad. Also, show your TA/AI the output of running the program as well as the output of`make vector-memcheck`

.