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,
}
Campbell Ritchie wrote:If you want to keep the memory locations simple, you can fit 128 numbers into 128 bits if you bits represent absence and presence of each element. You would do well to learn about how integer values are represented in two's complement notation. Also about the bitwise and/or operators. Try putting two numbers together with & and | and see what happens. Then you can work out how to get 128 numbers between 0 and 127 into the 16 bytes occupied by four ints (or two longs).
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