Быстрая побитовая манипуляция в Java

Question

Я пытаюсь создать программу, которая быстро генерирует определенную последовательность.

Последовательность дается через итерации, и идет следующим образом:

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

Пример:

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] 

Я хочу, чтобы это так быстро, как это возможно, и я полагал, что поскольку последовательность будет содержат только -1 или 1, я могу использовать побитовые операции, и каждый бит представляет true или false, который затем можно сопоставить с -1 или 1.

Затем я получаю последовательность бит, которую я могу манипулировать с помощью побитовых операций. У меня есть пользовательский класс, который создает long[] и куски бит в 64-битных кусках.

Все работает, и я получаю правильный ответ, но это решение намного медленнее, чем просто использование массива byte[] и петлевого желоба.

Самая трудоемкая функция - это та, которая меняет порядок бит и инвертирует каждый бит.

Прямо сейчас это выглядит следующим образом:

//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); 
} 

Есть ли способ, чтобы улучшить производительность здесь? Я новичок в побитовых операциях.

РЕДАКТИРОВАТЬ: Вот пользовательский класс со всеми соответствующими методами.

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])); 
} 

} 

Answer 1

Вы можете попробовать BitSet хотя он обычно сохраняет биты, которые установлены таким образом, что может понадобиться, чтобы следить за количеством битов вы заинтересованы в:

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(); 
} 

Answer 2

Вы Ждут» t запросите его, но существует прямая формула для вашей последовательности:

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(); 
}