CS140: Homework 10
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.
- Exercise 5.1 in the Weiss text. Just draw the diagrams and use
singly-linked lists for separate chaining.
- 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.
- Write a function that takes a non-negative integer, n,
as a parameter and that returns 2n 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.
- 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 < 2x and then
use 2x-1 as your table size. For example, if
n is 11, then x is 4 and the table size should be
24-1 = 15.
Write a function that takes a non-negative integer, n,
as a parameter and returns 2x-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.
- 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.
- 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.
- 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.