You are to write a program using a programming language of your choice to compute the

intersection and union of two sets A and B. The Universe set has 128 elements numbered from 1

to 128. That is Universe = {1, 2, 3, 4,…, 128}. Your program must use NO more than 16 memory

locations to represent four sets A, B, C, and D. The elements of each set are represented in bitformat.

An element in a set is marked by a 1. The missing elements are marked by a 0. For

example,

unsigned a[0] = 0x80010001,

a[1] = 0x80010001,

a[2] = 0x80010001,

a[3] = 0x80010001;

defines the elements of set A in bit-format. The elements are numbered from left to right. For

example, bit-pattern of a[0] indicates that elements 1, 16, and 32 are in set A, bit-pattern of a[1]

indicate that elements 33, 48, and 64 are also in set A, and so on.

Do the following:

1) Determine the elements of C = A intersection B in bit-format. Hint: Use the bit-wise AND

operator (&). Print set C in bit-format.

2) Determine the elements of D = A union B in bit format. Hint: Use the bit-wise OR operator

( | ). Print set D in bit-format.

3) Convert the bit-format of sets C and D to the list of actual elements. Specifically, write a

function and call it twice once passing set C and second time passing set D. This

function converts the bit-pattern to a list of actual elements. A sample output for set A is

given below.

4)

Test your program with the following two test data sets:

a)

unsigned a[4] = {0x80010001, 0x80010001, 0x80010001, 0x80010001};

unsigned b[4] = {0x80000001, 0x80000001, 0x80000001, 0x80000001};

b)

unsigned a[4] = {0x80000001, 0x80000001, 0x80000001, 0x80000001};

unsigned b[4] = {0x00000001, 0x80000000, 0x80000001, 0x80000001};

5) Turn in a hard copy of your program and the outputs for two test data sets. If you work

in teams of two see the note above.

Hint: Learn about bit-wise AND (&) and bit-wise OR ( | ) operators. Also learn about the rightshift

operator (>>) and “unsigned” data type (also see the note below). To convert a bit-format

to its corresponding element-list, you need to AND each 32-bit, bit-format, with 0x80000000 to

get the element 1 if the AND result is != 0, then AND it with 0x40000000 to get the element 2 if

the AND result != 0, then 0x20000000, etc. Note that you need to work with unsigned data types

otherwise a 1-bit right-shift of, say, 0x80000000 (i.e., 0x800000000 >> 1) will return

0xC0000000 (the result of arithmetic right-shift by 1) instead of 0x40000000.

“unsigned” data type: “unsigned” data type is not supported in Java. If you are using Java, use

signed data type but you need to mask the sign bit after the first shift (however, you could do this

after each shift to reduce code size). For example,

s = 0x80000000;

. . .

. . .

s = s >> 1;

s = s & 0x7FFFFFFF; //will make sign bit 0

Sample output for converting a bit-format to its corresponding list: Shown for set A for

test data a.

A = {

1,

16,

32,

33,

48,

64,

65,

80,

96,

97,

112,

128,

}