Java Sets Project
Devin Henderson
Greenhorn
Posts: 16
posted 6 years ago
I just destroyed my whole post here because I doubt anyone wants to read all of the directions. So, I am going to just ask some questions here in hoping of gaining some clarification.
My only question at this time is this:
I need to convert a bitpattern such as "0x8001001" to a list of actual elements. How would I go about doing that?
My only question at this time is this:
I need to convert a bitpattern such as "0x8001001" to a list of actual elements. How would I go about doing that?
Devin Henderson
Greenhorn
Posts: 16
posted 6 years ago
Hard to know how to answer that question. So, I will respost the directions for the assignment as that may have the answer you looking for:
Right now, I am trying to do step 1 and 2.
Right now, I am trying to do step 1 and 2.
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 bitformat. The elements are numbered from left to right. For
example, bitpattern of a[0] indicates that elements 1, 16, and 32 are in set A, bitpattern 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 bitformat. Hint: Use the bitwise AND
operator (&). Print set C in bitformat.
2) Determine the elements of D = A union B in bit format. Hint: Use the bitwise OR operator
(  ). Print set D in bitformat.
3) Convert the bitformat 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 bitpattern 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 bitwise AND (&) and bitwise OR (  ) operators. Also learn about the rightshift
operator (>>) and “unsigned” data type (also see the note below). To convert a bitformat
to its corresponding elementlist, you need to AND each 32bit, bitformat, 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 1bit rightshift of, say, 0x80000000 (i.e., 0x800000000 >> 1) will return
0xC0000000 (the result of arithmetic rightshift 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 bitformat 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
Marshal
Posts: 52664
122
posted 6 years ago
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).
Devin Henderson
Greenhorn
Posts: 16
posted 6 years ago
I will be honest. I have no idea about anything you just said. I just started programming about 23 months ago and I am not the only one that feels that this program is completely out of reach. If you can simply whatever you said above, it would be greatly appreciated.
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).
I will be honest. I have no idea about anything you just said. I just started programming about 23 months ago and I am not the only one that feels that this program is completely out of reach. If you can simply whatever you said above, it would be greatly appreciated.
Devin Henderson
Greenhorn
Posts: 16
posted 6 years ago
Still looking for an answer to my original question.
How do I convert a bitpattern such as "0x8001001" to a list of actual elements?
There is the following HINT in the assignment, but I cannot figure out what to break it down logically into psuedocode:
Thanks!
How do I convert a bitpattern such as "0x8001001" to a list of actual elements?
There is the following HINT in the assignment, but I cannot figure out what to break it down logically into psuedocode:
Hint: Learn about bitwise AND (&) and bitwise OR (  ) operators. Also learn about the rightshift
operator (>>) and “unsigned” data type (also see the note below). To convert a bitformat
to its corresponding elementlist, you need to AND each 32bit, bitformat, 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 1bit rightshift of, say, 0x80000000 (i.e., 0x800000000 >> 1) will return
0xC0000000 (the result of arithmetic rightshift 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
Thanks!
Campbell Ritchie
Marshal
Posts: 52664
122
posted 6 years ago
Have a look at the Java™ tutorials where there is a short section about bitwise operators.
If you have a certain number of bits, maybe 8, that gives you a capacity for storage. 8 bits will store 256 different numbers, for example. Java byte, short, int and long numbers are all stored in two's complement form, for 8, 16, 32 and 64 bits respectively. In complement arithmetic, one usually has half the range as negative (in 8 bits = 128 numbers, from 1 to 128 inclusive) and the other half as not negative (0 to 127 inclusive makes 128 numbers).
The nonnegative numbers are written as one expects, eg 0000_0000 = 0, 0000_0001 = 1, 0000_0010 = 2, 0000_0011 = 3, 0001_0000 = 0x10 = 16, 0111_1111 = 0x7f = 127).
The negative numbers are made by subtraction; take the sign off and subtract the number from the capacity, so for 1 you subtract 1 from 256, etc.
1_0000_0000
_0000_0001
_1111_1111, or for 128:
1_0000_0000
_1000_0000
_1000_0000.
As you see, you can get any other number in between similarly. There is a shortcut where one inverts the bits and adds 1. there is another shortcut whereby the rightmost (no 0) bit means 2^0 = 1, the next (no 1) bit means 2^1 = 2, etc, but the leftmost bit (no 7) means (2^7) = minus128. You can simply add all the bits like that and get the value of the number.
Try the bitwise ~ complement, & and, ^ xor,  or and shift (<< >> >>>) operators and see what they do. Work out why 1 & 2 give 0, why 1  2 gives 3, why 1 ^ 2 gives 3 too, why 1 << 2 gives 4 and 1 >> 2 gives 0. I wrote about the shift operators two years ago, here.
Two's complement arithmetic has the advantage that there is no waste of memory (256 is the absolute maximum capacity and 8 bits actually hold 256 values, whereas some other formats only hold 255 different values), and that the addition chip can be used for subtraction simply by inserting a bank of XOR gates.
If you have a certain number of bits, maybe 8, that gives you a capacity for storage. 8 bits will store 256 different numbers, for example. Java byte, short, int and long numbers are all stored in two's complement form, for 8, 16, 32 and 64 bits respectively. In complement arithmetic, one usually has half the range as negative (in 8 bits = 128 numbers, from 1 to 128 inclusive) and the other half as not negative (0 to 127 inclusive makes 128 numbers).
The nonnegative numbers are written as one expects, eg 0000_0000 = 0, 0000_0001 = 1, 0000_0010 = 2, 0000_0011 = 3, 0001_0000 = 0x10 = 16, 0111_1111 = 0x7f = 127).
The negative numbers are made by subtraction; take the sign off and subtract the number from the capacity, so for 1 you subtract 1 from 256, etc.
1_0000_0000
_0000_0001
_1111_1111, or for 128:
1_0000_0000
_1000_0000
_1000_0000.
As you see, you can get any other number in between similarly. There is a shortcut where one inverts the bits and adds 1. there is another shortcut whereby the rightmost (no 0) bit means 2^0 = 1, the next (no 1) bit means 2^1 = 2, etc, but the leftmost bit (no 7) means (2^7) = minus128. You can simply add all the bits like that and get the value of the number.
Try the bitwise ~ complement, & and, ^ xor,  or and shift (<< >> >>>) operators and see what they do. Work out why 1 & 2 give 0, why 1  2 gives 3, why 1 ^ 2 gives 3 too, why 1 << 2 gives 4 and 1 >> 2 gives 0. I wrote about the shift operators two years ago, here.
Two's complement arithmetic has the advantage that there is no waste of memory (256 is the absolute maximum capacity and 8 bits actually hold 256 values, whereas some other formats only hold 255 different values), and that the addition chip can be used for subtraction simply by inserting a bank of XOR gates.
Pay attention! Tiny ad!
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/ThreadBoostfeature
