Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Left rotate array of longs

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello,

I've spent literally all day trying to find a solution to this issue, without success.

I have an array of longs of size 2, where the first element represents the left half and the second element represents the right half of a 128-bit number. Since there is no data type which supports 128-bit values on java, I used the array of longs as the next best thing.
I need to somehow combine (or without combining if possible) these two halves and perform a bitwise left rotation of k bits on them, and finally convert them back to longs (long array). I can't seem to find a solution to this. I tried using BigInteger as a structure to hold the whole number, and then perform a combination of left-shift, right-shift operations which you normally would do on integers, longs, but without luck.
Trying to manipulate at the bit-level without combining the two longs seems impossible.
I would love to hear from you guys any suggestions, ideas or how to's on how to find a solution to this.
 
Ranch Hand
Posts: 86
18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello,

I would split the rotation in two steps (and write it for any array size, not only 2):
1) Rotate the complete array so that each element requires only a rotation of [0..63]
2) Rotate the elements by this remaining rotation factor. Each resulting long consists of its previous bits shifted to the left and the bits of the next lower long that will be shifted out (whereas the 0th long gets the overflowing bits from the highest long).
 
Aleks Blain
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tobias Bachert wrote:Hello,

I would split the rotation in two steps (and write it for any array size, not only 2):
1) Rotate the complete array so that each element requires only a rotation of [0..63]
2) Rotate the elements by this remaining rotation factor. Each resulting long consists of its previous bits shifted to the left and the bits of the next lower long that will be shifted out (whereas the 0th long gets the overflowing bits from the highest long).



First of all, thank you for your interest in my issue.
I'm not really understanding your idea, if you could be a little more specific, I would appreciate that.
On both points I m not sure how I would achieve them.
 
Saloon Keeper
Posts: 13282
292
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you taken a look if the BitSet class can help you?
 
Aleks Blain
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well I just found out today earlier about the BitSet class. It gave me hope it can be done, so I am trying to get it to work. Here is what I have now:

r - represents the number of positions of a bit to be shifted
c - is the byte[] array of length 16 containing the converted long[0], and long[1]
s- BitSet object, created from c
t - temporary BitSet object which will hold the first r elements of c, that will be added to the last 128-r positions after the other values have been shifted


But in the end it does not work, I'm not sure what is wrong with it, or if I'm using BitSet right.
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A bitset is most likely not helpful as it does not offer any shift methods.

I can't be more specific without actual code, thus below my solution.
n>>6 is the short version of n / 64 - (n % 64 < 0 ? 1 : 0) and represents the required rotation of the complete array for step 1 (0 <= rotation - arrayrotation * 64 < 64).
The code after the rotate call represents step 2 (shifts of longs are implicit modulo 64, as a result the provided rotation value can be used for the shifts)
(I assume it is ok to post a solution as this thread was posted in the general forum and not the beginning forum - if this is not the case please delete it.)

Edit: removed mask as it was not required
 
Aleks Blain
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tobias Bachert wrote:A bitset is most likely not helpful as it does not offer any shift methods.

I can't be more specific without actual code, thus below my solution.
n>>6 is the short version of n / 64 - (n % 64 < 0 ? 1 : 0) and represents the required rotation of the complete array for step 1 (0 <= rotation - arrayrotation * 64 < 64).
The code after the rotate call represents step 2 (shifts of longs are implicit modulo 64, as a result the provided rotation value can be used for the shifts)
(I assume it is ok to post a solution as this thread was posted in the general forum and not the beginning forum - if this is not the case please delete it.)

Edit: removed mask as it was not required



First of all thank you investing your time on this, really appreciate it!
Now I hope this is my last stupid question ArrayUtil is from which library exactly?
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It's from my personal library - you have to implement it yourself (java.util.Collections#rotate could be a good orientation for a good implementation (juggling of the elements)) (or find another library that provides a method to rotate arrays).
 
I don't always make ads but when I do they're tiny
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic