java - 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 位 block 。

一切正常，我得到了正确的答案，但这个解决方案比仅使用 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

你没有要求它，但你的序列有一个直接的公式:

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