cancel
Showing results for 
Search instead for 
Did you mean: 

A challenge for anyone who wants one : )

Former Member
0 Kudos

Hi, I am trying to write a method that basically takes in a vector containing short objects which have variable legnth codes in them. I want to manipulate these shorts and create a new Vector of shorts that contain fixed length code versions of these;

Right now you can think of the shorts as overlapping on its neighbour in the vector, some of the bits are spilling over into the next short.

Heres an example to make it clearer

every short should have two parts, a 3 bit 'id' that tells the algorithm how many bits folling these 3 bits are to be associated with the id. The id can be used to get this number of bits from an array:

indexlengths[] = {7, 6, 8, 5, 4, 7, 9, 8}

so, when the algorithm encounters id #2 (the in the 3 leftmost bits) it looks in this array in position 2 and then knows that following the id is 6 bits to be extracted. once this has been extracted a new short should created and, these 6 bits should be added but shifted over to the very right of the short(shifted 13-6 in this case) and this id should added but to the very leftmost 3 bits.

so:

010 1111110100000

(id:2) (6 bits)

should go to:

010 0000000111111

now this wouldn't be too much of a problem BUT the remaining bits that were discarded (in this case 0100000) must be kept and plugged to the next short in the vector

so if the next short in the vector is

1010000011111110

it will have this remainder from the previous short plugged into the right of it

010 0000101000001 and 'pushed' off is:1111110

now this process must continue making sure that this remainder that was 'pushed' off in plugged in to the next short BUT FIRST the process that we started with must be applied, a new short is created(for which the resulting fixed legnth code will be stored in), the ID is extracted from the leftmost 3 bits (id: 0) of the current short and the number of bits to follow is found from the above array indexLengths[0] which is 7 bits. these 7 bits are shifted by (16-3)-7 = 6 positions to the right so they are stored in to the rightmost part of this new short and the id will stay at the leftmost 3 bits:

010 0000000000101 'pushed off: 000001'

so now we have both 1111110 and 000001 'pushed' off of the same short, as the length of bits of this remainder gets longer and reaches 16, a new short should be created and added to the result vector.

One more example just to show it visually:

this time the indexes after the 'id' part are all 6

int[] indexLengths = {6, 6, 6, 6, 6, 6, 6, 6};

a vector of 3 shorts:

111 1000011111111, 011 0111111100000, 101 1000000000000,

results in:

111 0000000100001, 111 1111011 011111, 110 00001011000000, 000000

looking at the first resulting short:

(id) (6 bits that followed the index shifted to the right most 6 bits)

111 0000000100001

the remiander that had to be 'pushed off' is inserted in to the start of the next short and the process starts again.

I know this is alot to ask, but any tips would be great, java isn't being any help when working with bits and shorts, for example when extracting the id (using a mask and then shifting to the right 13 places) I get negative numbers sometimes!

Any suggestions on how to break this down into a managable problem to solve would be great too : )

Thanks!

Accepted Solutions (0)

Answers (1)

Answers (1)

Sigiswald
Contributor
0 Kudos

Hi Ross,

Although I did try to understand what exactly you're trying to do, you got me completely lost at the "BUT FIRST" part.

Can you maybe check your examples for possible mistakes? e.g. in your 1st example, id 2 corresponds to 6 bits, but according to the indexlengths array, it should've been 8 bits since indexlengths[2] == 8; or you say "it will have this remainder from the previous short plugged into the right of it" where you probably mean left instead.

Then the BUT FIRST part, can you clarify a few things?

"[...] a new short is created(for which the resulting fixed legnth code <b>(which resulting fixed length code?)</b> will be stored in), the ID is extracted from the leftmost 3 bits (id: 0) of the current short <b>(what's the current short? the 1st or the 2nd item in your vector)</b> and the number of bits to follow is found from the above array indexLengths[0] which is 7 bits. these 7 bits <b>(exactly which 7 bits?)</b> are shifted by (16-3)-7 = 6 positions to the right so they are stored in to the rightmost part of this new short and the id will stay at the leftmost 3 bits [...]"

The 2nd example is clear, except the "and the process starts again" part.

You say "when extracting the id (using a mask and then shifting to the right 13 places) I get negative numbers sometimes!" When you do a right-shift, you do use an unsigned right-shift?

Anyway, two useful items are

1. <a href="http://www.janeg.ca/scjp/oper/shift.html">Shift Operators</a> and <a href="http://www.janeg.ca/scjp/oper/bitwise.html">Bitwise Operators</a>

2. have a look at the java.util.BitSet class

Kind regards,

Sigiswald

Former Member
0 Kudos

Hi! Thank you so much for responding.

first of all, yes you are correct id 2 should correspond to 8. Again you are correct when you say I meant to the left of it : )

I definitately didn't do this in my attempt, just a few slips ups while explain it!

On to the BUT FIRST part:

the resulting fixed length code is the result, initially the codes are variable length and the ID part can occur anyway in a short, in the result it will always have ID as the 3 leftmost bits and 13 bits following it (this part is now fixed length).

the current short is the one currently taken from the vector to be manipulated, the algorithm works on one short at a time, remembering how many bits spilled over from the last iteration (after manipulating the previous short) and what the value of these bits were. This is at least how I approached it.

"These 7 bits" means the 7 bits directly following the ID part, for example:

111 1111111000000000

id 7 bits (part to be plugged in to the next short)

When I said "the process starts again" I was refering to the first short in the example and how the algorithm continues iteratively. If you understood the 2nd example then that means you've got it.

I'll take a look at those pages soon and post my attempt solutions also.

Thanks again! I owe you one

Sigiswald
Contributor
0 Kudos

Hi Ross,

I think I got it

But let me ask you 2 questions.

1. What exactly do you mean by "[a vector containing] short objects"? Are these "short objects" actually objects of type java.lang.Short? Or rather java.lang.String objects that you then convert to some binary representation? I mean, where do they come from? Maybe you just read a bunch of bytes from some InputStream?

2. How many shorts/bytes are there? If it's a rather small amount, it's likely better to have some easy to understand code that hasn't got an excellent performance. But if you have to deal with large amounts, performance is much more important.

Kind regards,

Sigiswald

Sigiswald
Contributor
0 Kudos

Hi Ross,

Here are a few links (same site) I'm sure you'll find very interesting.

<a href="http://mindprod.com/jgloss/binary.html">binary</a>

<a href="http://mindprod.com/jgloss/bitcount.html">bit count</a>

<a href="http://mindprod.com/jgloss/masking.html">masking</a>

Kind regards,

Sigiswald