Devin Henderson

Greenhorn

Posts: 16

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

Devin Henderson

Greenhorn

Posts: 16

posted 7 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 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

Sheriff

Posts: 55351

157

posted 7 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

`int`s (or two`long`s).
Devin Henderson

Greenhorn

Posts: 16

posted 7 years ago

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.

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 fourints (or twolongs).

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

Posts: 16

posted 7 years ago

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:

Thanks!

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

Posts: 55351

157

posted 7 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

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

_1111_1111, or for -128:

1_0000_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) =

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 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) =

__minus__128. 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.