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)

When N> 32, we can represent a set not by a long integer, but by an array of K long integers, where K is the quotient by excess of N by 32. 

We set up here a so-called paging mechanism. Since we know how to do with sets of 32 values, to manage sets of N values it suffices to see them as K packets, or pages, of 32 elements, K being the quotient by excess of N by 32.
To reach the ith element it is enough then to calculate the index of the page which concerns it (i / 32) then its rank in this page (i% 32).

#include <stdio.h>
#include <stdlib.h>
#define N 100
#define K ((N + 31) / 32)

typedef struct 
{
	unsigned long tab[K]; 
} SET;


void toempty(SET *e) 
{
	int i;
	for (i = 0; i < K; i++)
		e->tab[i] = 0;
}

int empty(SET e) 
{
	int i;
	for (i = 0; i < K; i++)
		if (e.tab[i] != 0)
			return 0;
	return 1;
}

int find(int x, SET e) 
{
	return (e.tab[x / 32] & (1L << (x % 32))) != 0;
}

void add(int x, SET *e) 
{
	e->tab[x / 32] |= (1L << (x % 32));
}

void removeS(int x, SET *e) 
{
	e->tab[x / 32] &= ~(1L << (x % 32));
}   

void intersect(SET e1, SET e2, SET *r) 
{
	int i;
	for (i = 0; i < K; i++)
		r->tab[i] = e1.tab[i] & e2.tab[i];
}

void unionS(SET e1, SET e2, SET *r) 
{
	int i;
    	for (i = 0; i < K; i++)
		r->tab[i] = e1.tab[i] | e2.tab[i];
}

void complement(SET e, SET *r) 
{
	int i;
	for (i = 0; i < K; i++)
		r->tab[i] = ~e.tab[i];
}

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;
}