This homework assignment asks you to write a number of functions involving bit operations. You do not have to compile or execute the functions and you may assume that the parameters are error-free. All of the function bodies should requires only a few lines of code. Three of them can be done with a single line of code.

1. Exercise 5.1 in the Weiss text. Just draw the diagrams and use singly-linked lists for separate chaining.

2. Explain why open address hashing could be problematic if deletions are allowed and if hash table entries are marked empty when the deletion occurs. Suggest a solution that would solve this problem. I do not want you to write code, just provide a couple sentence explanation of how you would solve the problem.

3. Write a function that takes a non-negative integer, n, as a parameter and that returns 2ⁿ as the result. Your function should consist of a single line of code and hence will need to make use of the bit operations you learned about in class.

4. In class I indicated that one common way to choose a table size for a hash table is to find an integer which is the smallest power of two greater than the estimated number of elements in the data set and then to subtract one from it. In other words, if n is the estimated number of elements in the data set, determine the smallest x such that n < 2^x and then use 2^x-1 as your table size. For example, if n is 11, then x is 4 and the table size should be 2⁴-1 = 15.

   Write a function that takes a non-negative integer, n, as a parameter and returns 2^x-1 as the result. if n is 11, your function should return 15. If it is 32 your function should return 63. Although you can solve this problem by writing a for loop that repeatedly divides n by 2, I want you to solve the problem using bit shifting. It is legitimate to divide a number by 2 by bit-shifting it. Hint: Think of n as a string of bits. For example, 13 can be represented as 1101 using bits. If bit positions are numbered from right to left with the first bit position being numbered 1, then x is equal to the bit position of the last 1 in the string. In the above example the last 1 will be in bit position 4.

5. Write a function that takes an unsigned integer, n, and two non-negative integers, left, and right as parameters. Your function should pretend that n is a bit string and print the bits between and including left and right. You should assume that bit positions are numbered from 32 to 1. For example, if n can be represented as 10110111011000011101011011010010 and left is 30 and right is 24, your function should print "1101110":

   	         10110111011000011101011011010010
   	position:  3     2
   		   0     4
           

   Hint: Use bit-shifting.

6. Write a function that takes an unsigned integer, n, and an index index between 1 and 32. Return the value of the bit, either 0 or 1, at the index location. Assume that bit positions are numbered from 32 to 1. If the bit string from the previous problem is passed to your function with the index 30, it would return 1. Hint:Your answer will need to include both a bit shifting operation and either a bitwise and or a bitwise or operation.

7. Write a function that takes an unsigned integer, n, and an index index between 1 and 32. It should return the original integer, modified so that the indicated bit is set to 1. Assume that bit positions ar numbered from 32 to 1. For example, if the bit string from problem 5 is passed to your program with the index 24, you would return the string:

   	         10110111111000011101011011010010
   	position:        2
   		         4
           

   Hint:Your answer will need to include both a bit shifting operation and either a bitwise and or a bitwise or operation.