You are asked to give an implementation of the ADT set using an array of bits and having the following functions:

• void toempty(SET *S)
• int empty(SET S)
• int find(int x, SET S)
• void add(int x, SET *S)
• void removeS(int x, SET *S)
• void intersect(SET S1, SET S2, SET *R)
• void unionS(SET S1, SET S2, SET *R)
• void complement(SET S, SET *R)
• void display(SET S)

Here, we assume that N ≤ 32. A set is represented by a long integer (without sign), with the convention $$i \in  e \rightarrow$$ the $$i$$th bit of e is 1.

This implementation of sets is a classic of C courses, since it represents one of the rare "admirable" uses of operators on bits:

• a & b: calculation of a number whose ith bit is the conjunction of the ith bit of a with the ith bit of b.
• a | b: calculation of a number whose ith bit is the disjunction of the ith bit of a with the ith bit of b.
• ~ a: calculation of a number whose ith bit is the opposite of the ith bit of a.
• a << n: calculation of a number whose bits are those of a, shifted by n positions to "the left" (the side of the "most significant"). The n bits on the left are lost. ( i.e. on the right enter n bits to 0).
• a >> n: calculation of a number whose bits are those of a, shifted by n positions to "the right" (the side of the units). The n right bits are lost. On the left enter:
  • if a is of an unsigned type, enter n bits 0,
  • if a is of a signed type, n copies of the leftmost bit of a.

The basic idea is simple: store the binary information "i belongs to e" in the bits of a long integer rather than in the bytes of an array of bytes.

#include <stdio.h>
#include <stdlib.h>

#define N 32

typedef unsigned long SET;

void toempty(SET *e) 
{
	*e = 0;
}

int empty(SET e) 
{
	return e == 0;    
}

int find(int x, SET e) 
{
	return (e & (1L << x)) != 0;
}

void add(int x, SET *e) 
{
	*e |= (1L << x);
}

void removeS(int x, SET *e) 
{
	*e &= ~(1L << x);
}   

void intersect(SET e1, SET e2, SET *r) 
{
	*r = e1 & e2;
}

void unionS(SET e1, SET e2, SET *r) 
{
	*r = e1 | e2;
}

void complement(SET e, SET *r) 
{
	*r = ~e;
}

void display(SET e) 
{
	int i;
    
	printf("[ ");
	for (i = 0; i < N; i++)
		if (find(i, e))
			printf("%d ", i); 
	printf("]");
}


int main() 
{
	SET a, b, c;
	int i;
    
	toempty(&a);
	for (i = 0; i < 32; i += 2)
		add(i, &a);
	for (i = 30; i >= 0; i -= 3)
		add(i, &a);
	printf("  a : "); 
	display(a); 
	printf("\n");
    
	toempty(&b);
	printf("a empty? %s\n", empty(a) ? "yes" : "no");    
	printf("b empty? %s\n", empty(b) ? "yes" : "no");
	for (i = 0; i < 32; i += 5)
		add(i, &b);
	printf("  b : "); 
	display(b); 
	printf("\n");
    
	complement(b, &c);
	printf(" ~b : "); 
	display(c); 
	printf("\n");
    
	intersect(a, b, &c);
	printf("a.b : "); 
	display(c); 
	printf("\n");
    
	unionS(a, b, &c);
	printf("a+b : "); 
	display(c); 
	printf("\n");
  
	for (i = 0; i < 32; i += 3)
		removeS(i, &c);
	printf("c : "); 
	display(c); 
	printf("\n");
    
	return 0;
}