java 128 bit structure bit maninpulation

Question

Is there a way to create a 128 bit object in java, that can be bit manipulated the same way as a long or int? I want to do 32 bit shifts and i want to be able to do a bit OR operation on the whole 128 bit structure.

Answer 1

Here, I present to you... an old idea. Now it's awfully downgraded (no code enhancer, no nothing) to simple 128 bit thingie that should be super fast, though. What I truly want is a ByteBuffer based array of C alike Struct but fully usable in java.

The main idea is allocating more than a single object at a time and using a pointer to the array. Thus, it greatly conserves memory and the memory is allocated in continuous area, so less cache misses (always good).

I did some moderate testing (but the code is still untested). It does allow basic operations like add, xor, or, set/get with 128 bit numbers. The standard rule: less documentation than expected applied unfortunately. Adding extra code for extra operations should be straight forward.

Here is the code, look at main method for some usage. Cheers!

package bestsss.util;

import java.util.Random;

public class Bitz {
    final int[] array;
    private Bitz(int n){
        array=new int[n<<2];
    }

    public int size(){
        return size(this.array);
    }

    private static int size(int[] array){
        return array.length>>2;
    }
    /**
     * allocates N 128bit elements. newIdx to create a pointer
     * @param n
     * @return
     */
    public static Bitz allocate(int n){
        return new Bitz(n);
    }
    /**
     * Main utility class - points to an index in the array
     * @param idx
     * @return
     */
    public Idx newIdx(int idx){     
        return new Idx(array).set(idx);
    }

    public static class Idx{
        private static final  long mask = 0xFFFFFFFFL;
        //dont make the field finals

        int idx;
        int[] array;//keep ref. here, reduce the indirection

        Idx(int[] array){
            this.array=array;
        }

        public Idx set(int idx) {
            if (Bitz.size(array)<=idx || idx<0)
                throw new IndexOutOfBoundsException(String.valueOf(idx));

            this.idx = idx<<2;
            return this;
        }

        public int index(){
            return idx>>2;
        }

        public Idx shl32(){
            final int[] array=this.array;
            int idx = this.idx;

            array[idx]=array[++idx];
            array[idx]=array[++idx];
            array[idx]=array[++idx];                 
            array[idx]=0;

            return this;
        }

        public Idx shr32(){
            final int[] array=this.array;
            int idx = this.idx+3;

            array[idx]=array[--idx];
            array[idx]=array[--idx];
            array[idx]=array[--idx];                 
            array[idx]=0;
            return this;
        }
        public Idx or(Idx src){         
            final int[] array=this.array;
            int idx = this.idx;

            int idx2 = src.idx;
            final int[] array2=src.array;

            array[idx++]|=array2[idx2++];
            array[idx++]|=array2[idx2++];
            array[idx++]|=array2[idx2++];
            array[idx++]|=array2[idx2++];

            return this;            
        }

        public Idx xor(Idx src){            
            final int[] array=this.array;
            int idx = this.idx;

            int idx2 = src.idx;
            final int[] array2=src.array;

            array[idx++]^=array2[idx2++];
            array[idx++]^=array2[idx2++];
            array[idx++]^=array2[idx2++];
            array[idx++]^=array2[idx2++];

            return this;            
        }

        public Idx add(Idx src){            
            final int[] array=this.array;
            int idx = this.idx+3;

            final int[] array2=src.array;
            int idx2 = src.idx+3;


            long l =0;

            l += array[idx]&mask;
            l += array2[idx2--]&mask;           
            array[idx--]=(int)(l&mask);
            l>>>=32;


            l += array[idx]&mask;
            l += array2[idx2--]&mask;           
            array[idx--]=(int)(l&mask);
            l>>>=32;

            l += array[idx]&mask;
            l += array2[idx2--]&mask;           
            array[idx--]=(int)(l&mask);
            l>>>=32;

            l += array[idx]&mask;
            l += array2[idx2--];            
            array[idx]=(int)(l&mask);
//          l>>>=32;

            return this;            
        }

        public Idx set(long high, long low){
            final int[] array=this.array;
            int idx = this.idx;
            array[idx+0]=(int) ((high>>>32)&mask);
            array[idx+1]=(int) ((high>>>0)&mask);


            array[idx+2]=(int) ((low>>>32)&mask);
            array[idx+3]=(int) ((low>>>0)&mask);
            return this;
        }


        public long high(){
            final int[] array=this.array;
            int idx = this.idx;
            long res = (array[idx]&mask)<<32 | (array[idx+1]&mask); 
            return res;
        }

        public long low(){
            final int[] array=this.array;
            int idx = this.idx;
            long res = (array[idx+2]&mask)<<32 | (array[idx+3]&mask); 
            return res;
        }

        //ineffective but well
        public String toString(){                   
            return String.format("%016x-%016x", high(), low());
        }
    }

    public static void main(String[] args) {
        Bitz bitz = Bitz.allocate(256);
        Bitz.Idx idx = bitz.newIdx(0);
        Bitz.Idx idx2 = bitz.newIdx(2);

        System.out.println(idx.set(0, 0xf));
        System.out.println(idx2.set(0, Long.MIN_VALUE).xor(idx));       

        System.out.println(idx.set(0, Long.MAX_VALUE).add(idx2.set(0, 1)));
        System.out.println("==");
        System.out.println(idx.add(idx));//can add itself

        System.out.println(idx.shl32());//left
        System.out.println(idx.shr32());//and right
        System.out.println(idx.shl32());//back left

        //w/ alloc
        System.out.println(idx.add(bitz.newIdx(4).set(0, Long.MAX_VALUE)));

        //self xor
        System.out.println(idx.xor(idx));
        //random xor

        System.out.println("===init random===");
        Random r = new Random(1112); 
        for (int i=0, s=bitz.size(); i<s; i++){
            idx.set(i).set(r.nextLong(), r.nextLong());
            System.out.println(idx);
        }
        Idx theXor = bitz.newIdx(0);
        for (int i=1, s=bitz.size(); i<s; i++){         
            theXor.xor(idx.set(i));
        }

        System.out.println("===XOR===");
        System.out.println(theXor);
    }
}

Answer 2

Three possibilities have been identified:

• The BitSet class provides some of the operations that you need, but no "shift" method. To implement this missing method, you'd need to do something like this:

  BitSet bits = new BitSet(128);
  ...
  // shift left by 32bits
  for (int i = 0; i < 96; i++) {
      bits.set(i, bits.get(i + 32));
  }
  bits.set(96, 127, false);
  

• The BigInteger class provides all of the methods (more or less), but since BigInteger is immutable, it could result in an excessive object creation rate ... depending on how you use the bitsets. (There is also the issue that shiftLeft(32) won't chop off the leftmost bits ... but you can deal with this by using and to mask out the bits at index 128 and higher.)

• If performance is your key concern, implementing a custom class with 4 int or 2 long fields will probably give best performance. (Which is actually the faster option of the two will depend on the hardware platform, the JVM, etc. I'd probably choose the long version because it will be simpler to code ... and only try to optimize further if profiling indicated that it was a potentially worthwhile activity.)

  Furthermore, you can design the APIs to behave exactly as you require (modulo the constraints of Java language). The downside is that you have to implement and test everything, and you will be hard-wiring the magic number 128 into your code-base.

Answer 3

There is no longer data type than long (I have logged this as an RFE along with a 128 bit floating point ;)

You can create an object with four 32-bit int values and support these operations fairly easily.