CODEWITHSUNDEEP
javaoptimizationbitwise-operatorsbitset
maxb
maxb

Reputation: 655

Fast bitwise manipulation in Java

I'm trying to create a program that quickly generates a certain sequence.

The sequence is given through iteration, and goes as follows:

new = old + 1 + (-1*(old reversed))

Example:

old = [1]
new = [1]+[1]+[-1] = [1, 1, -1]

old = [1, 1, -1]
new = [1, 1, -1] + [1] + [1, -1, -1] = [1, 1, -1, 1, 1, -1, -1]

I want this to go as fast as possible, and i figured that since the sequence will only contain -1 or 1, I can use bitwise operations, and let every bit represent true or false, which I can then map to -1 or 1.

Then I end up with a sequence of bits which I can manipulate using bitwise operations. I have a custom class that creates a long[], and chunks up the bits in 64 bit pieces.

Everything is working, and I'm getting the correct answer, but this solution is a lot slower than just using a byte[] array and looping trough.

The most time-consuming function is the one that reverses the order of the bits, and inverts every bit.

Right now it looks like:

//this function is inside the custom class I defined
public void set(int n, int d) { //set bit n as the inverse value of bit d
    storage[n/64] ^= ~(storage[ind/64] & (1L << ind)) << (n-ind);
}

//sequence is an instance of my custom class 
//the length of the sequence is sequenceLength 
for (int i = 1; i < sequenceLength; i++) {
    sequence.set(sequenceLength+i, sequenceLength-i);
}

Is there any way to improve performance here? I'm quite new to bitwise operations.

EDIT: Here is the custom class with all relevant methods.

public class Dragon3 {

private FastStorage dragon;
private short[] xpos;
private short[] ypos;

public Dragon3(int n) {
    dragon = new FastStorage((int)Math.pow(2,n+1)-1);
    dragon.setSize(1);
    for (int i = 0; i < n; i++) {
        iterate(dragon);
    }

}

public class FastStorage {
    private long[] storage;
    private int size;

    public FastStorage(int n) {
        storage = new long[(n-1)/64+1];
        size = n;
    }
    public int getSize() {
        return size;
    }
    public void setSize(int n) {
        size = n;
    }
    public void set(int n, int ind) {
        storage[n/64] ^= (~storage[ind/64] & (1L << ind)) << (n-ind);
    }
    public long getInv(int n) {
        return ~(storage[n/64]) & (1L << n);            
    }

public void iterate(FastStorage drag) {
    int dragLength = drag.getSize();
    drag.setSize(2*dragLength+1);
    //drag.toggle(dragLength);
    for (int i = 1; i < dragLength+1; i++) {
        drag.set2(dragLength+i, dragLength-i);
        //drag.set(dragLength+i, drag.getInv(dragLength-i));
    }
}

public static void main(String[] args) {
    Dragon3 instance = new Dragon3(Integer.valueOf(args[0]));
}

}

Upvotes: 1

Views: 449

Answers (2)

Florian F
Florian F

Reputation: 1377

You didn't ask for it, but there is a direct formula for your sequence:

public static void main(String[] args) {
    for( int n=1 ; n<=15 ; n++ ){
        int fold = 1 - ((n/(n&-n))&2);
        System.out.print(" " + fold);
    }
    System.out.println();
}

Upvotes: 2

JimW
JimW

Reputation: 186

You could try a BitSet though it normally keeps track of the bits that are set so you might need to keep track of the number of bits you are interested in:

public static void main(String[] args) {
    BitSet bitSet = new BitSet();
    bitSet.set(0,true);
    bitSet.set(1, true);
    bitSet.set(2, false);

    final int length = 3;
    printBitSet(bitSet, length);

    BitSet newBitSet = new BitSet(length * 2 + 1);
    for (int i = 0; i <length; i++) {
        newBitSet.set(i, bitSet.get(i));
    }
    newBitSet.set(length, true);
    for (int i = 0; i < length; i++) {
        newBitSet.set(length + i + 1, !bitSet.get(length - i - 1));
    }
    printBitSet(newBitSet, 2*length +1);
}
private static void printBitSet(BitSet bitSet, int length) {
    for (int i = 0; i < length; i++) {
        System.out.print(" " +( bitSet.get(i) ? "1" : "-1"));
    }
    System.out.println();
}

Upvotes: 0

Related Questions