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 bit-pattern such as "0x8001001" to a list of actual elements. How would I go about doing that?

What are actual elements and what relation do they share with any bit-pattern?

Cheers,
Raj.

Devin Henderson
Greenhorn

Joined: Dec 01, 2009
Posts: 16

posted

0

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.

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,

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.

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

Joined: Dec 01, 2009
Posts: 16

posted

0

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 2-3 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

Joined: Dec 01, 2009
Posts: 16

posted

0

Still looking for an answer to my original question.

How do I convert a bit-pattern 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 psuedo-code:

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

Thanks!

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 42554

31

posted

0

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. Javabyte, 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 non-negative 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.