Description
Problem 1
Design and implement ADT SmallSet by treating a single unsigned int word as a bit vector and the positions as members of the universe:

Let N be sizeof(unsigned int). Then any subset of the universal set U = { 0, 1, … , N1 } can be represented as a bit vector of size N (which in turn can be stored as an int word.)
Given S U, for any j U, (j S) iff (j^{th} bit (counting 0 as the LSB) of S is 1)

Adding j to S can be implemented as setting j^{th} bit to 1; deleting as setting it to 0.
Obtaining j^{th} bit of an int in C can be achieved by masking the vector with a bit pattern and testing it: i.e.
(S & Bj) iff (j^{th} bit of S is 1) where Bj is all 0s except the j^{th} bit.
Bj can be obtained by leftshifting ((unsigned int) 1) j times.
Implement typical set operations union, intersect, and difference for this SmallSet ADT. You can use the following table for designing your functions.
Key 
Function 
Input Format 
Description 

0 
readData 
0NXY 
N represents the size of U (taken as input for convenience). X 

A1 A2 A3 .. Ax 
and Y represent the sizes of two sets of A & B respectively. 

B1 B2 B3 .. By 
You shall need to read two sets (A & B) of integers, separated 

by a new line. Each set contains values with space separation. 

Represent A and B in the form of SmallSet ADT described 

above. 

1 
Union 
1 
Perform union operation on A and B (C = A ∪ B) and print C. 

You may sort C in ascending order first before printing. 

2 
Intersection 
2 
Perform intersection operation on A and B (C = A ∩ B) and 

print C. 
You may sort C in ascending order first before 

printing. 

3 
Difference 
3 
Perform difference operation on A and B (C = A – B) and print 

C. 
You may sort C in ascending order first before printing. 

Sample input and output 

Sample Input 
Sample Output 

03256 
2479101516202124 

2415724 
15 

91615102021 
24724 

1 

2 

3 
1  P a g e