Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 25, 2024

// The program is in C programming language. // Below is the set.c file: #include set.h // Add an element with index v to the

// The program is in C programming language.

//Below is the set.c file:

#include "set.h"

// Add an element with index v to the set. // Returns -1 if v is negative or beyond the maximum capacity of the set. // Returns 0 if v is already in the set. // Returns 1 if v is successfully added. int add_element(int v) { return 0; }

// Remove an element with index v from the set. // Returns -1 if v is negative or beyond the maximum capacity of the set. // Returns 0 if v is already not in the set. // Returns 1 if v is successfully removed. int remove_element(int v) { return 0; }

// Checks if an element with index v is contained in the set. // Returns -1 if v is negative or beyond the maximum capacity of the set. // Returns 0 if v is not in the set. // Returns 1 if v is in the set. int contains_element(int v) { return 0; }

//Below is set.h :

#ifndef __SET #define __SET

#define N 100

// An array of unsigned integers that keeps a tally of what elements are // contained in the set. The total number of elements it can keep track of // is N x 32. unsigned int J[N];

int add_element(int v); int remove_element(int v); int contains_element(int v);

#endif

//Below given main function is just for testing purpose.

#include "set.h" #include #include

int main() { memset(J, 0, sizeof(J)); // set every bit in the array to 0

// Write your tests here. For example: //add_element(1); //add_element(24); //add_element(51); //add_element(66);

for (int i = 0; i < N; i++) { printf("%d ", J[i]); } printf(" "); return 0; }

Question:

We represent a set by an unsigned int array J with length N. Each bit in J represents a unique element. If a certain element is contained in our set, then the bit in J corresponding to that element is turned to 1, otherwise 0. We order the bits in J by counting from J[0] to J[N-1], and for each unsigned int from the least significant bit to the most. Consider the following example.

Suppose we have a collection of fruits. One way to represent them is to order them alphabetically and assign each fruit an index:

acai : 0

apple : 1

apricot : 2

avocado : 3

...

grape : 24

...

pineapple : 51

...

tangerine : 66

...

Remember we represent each fruit by 1 bit, starting from the least significant bit to the most. The bit is 1 if the fruit is in our set, 0 if not. Then the set

{acai}

is represented by 000...0001, i.e., J[0]=1.

The set

{acai, apricot}

is represented by 000...0101, i.e., J[0]=5.

Each component of J could keep track of 32 fruits, because there are 32 bits in an unsigned int. For the following set

{pineapple}

The corresponding bit falls into the i = (51 >> 5)th element of J, which is J[1]. (Right shifting by 5 is equivalent to dividing by 32.) The expression k = ((unsigned int)(51 << 27)) >> 27 will tell us which bit k in J[1] corresponds to pineapple. (Why is this?)

More generally, a set of fruits, e.g.,

{apple, grape, pineapple, tangerine}

will be represented by turning the 1st, 24th, 51st, and 66th bits in our unsigned int array to 1. Specifically,

apple corresponds to the 1st bit of J[0]
grape corresponds to the 24th bit of J[0]
pineapple corresponds to the 19th bit of J[1]
tangerine corresponds to the 2nd bit of J[2]

And our set {apple, grape, pineapple, tangerine} would be represented by an unsigned int array J where J[0] = 16,777,218, J[1] = 524,288, J[2] = 4, and every other component of J is 0. (You should calculate and verify that this is the case.)

We are asked to implement the following functions in set.c:

int add_element(int v): This function adds an element with index v to our set J.
int remove_element(int v): This function removes an element with index v from our set J.
int contains_element(int v): This function checks if an element with index v is contained in our set J.

We are only allowed to use bitwise operators &, |, ^, ~, <<, >>, as well as +, -, <, >. (We may not need all of them.) Arithmetic operators /, %, and * are not allowed.

main.c can be used for testing purpose.