在Java数组中排列位的最快方法

Question

随机（但重复）排列Java字节数组中所有位的最快方法是什么？我试着用一个位集成功地实现了这一点，但有没有更快的方法？显然，for循环占用了大部分cpu时间

我刚刚在IDE中做了一些评测，for循环占整个permute（）方法cpu时间的64%

为了澄清这一点，数组（preRound）包含一个进入过程的现有数字数组。我希望数组中的单个集合位以随机方式混合在一起。这就是P[]的原因。它包含位位置的随机列表。例如，如果设置了preRound的第13位，它将被转移到postwround的P[13]处。这可能在postRound的20555位置。整个过程是置换网络的一部分，我正在寻找最快的方法来置换输入的比特

到目前为止我的代码

 private byte[] permute(byte[] preRound) {
    BitSet beforeBits = BitSet.valueOf(preRound);
    BitSet afterBits = new BitSet(blockSize * 8);


    for (int i = 0; i < blockSize * 8; i++) {
        assert i != P[i];


        if (beforeBits.get(i)) {
            afterBits.set(P[i]);
        }
    }


    byte[] postRound = afterBits.toByteArray();
    postRound = Arrays.copyOf(postRound, blockSize);      // Pad with 0s to the specified length
    assert postRound.length == blockSize;


    return postRound;
}

仅供参考，blockSize大约为60000，p是一个随机查找表

Answer 1

< >我没有执行任何性能测试，但您可能要考虑以下事项： 忽略对数组的调用。copyOf（复制内部使用的long[]的副本，这有点烦人），只需设置最后一位，以防之前没有设置，然后取消设置

此外，还有一个很好的习惯用法，可以在输入排列中迭代设置位

private byte[] permute(final byte[] preRound) {
    final BitSet beforeBits = BitSet.valueOf(preRound);
    final BitSet afterBits = new BitSet(blockSize*8);
    for (int i = beforeBits.nextSetBit(0); i >= 0; i =
            beforeBits.nextSetBit(i + 1)) {
        final int to = P[i];
        assert i != to;
        afterBits.set(to);
    }
    final int lastIndex = blockSize*8-1;
    if (afterBits.get(lastIndex)) {
        return afterBits.toByteArray();
    }
    afterBits.set(lastIndex);
    final byte[] postRound = afterBits.toByteArray();
    postRound[blockSize - 1] &= 0x7F;
    return postRound;
}

如果它不切断它，如果你使用相同的P来进行多次迭代，那么考虑将置换转换成循环符号并在适当的位置执行转换可能是值得的。 通过这种方式，您可以在P上线性迭代，这可能使您能够更好地利用缓存（P是字节数组的32倍，假设它是int数组）。 然而，你将失去一个优势，那就是你只需要看1，最终会在字节数组中的每一位上移动，不管设置与否

如果要避免使用位集，可以手动操作：

private byte[] permute(final byte[] preRound) {
    final byte[] result = new byte[blockSize];
    for (int i = 0; i < blockSize; i++) {
        final byte b = preRound[i];
        // if 1s are sparse, you may want to use this:
        // if ((byte) 0 == b) continue;
        for (int j = 0; j < 8; ++j) {
            if (0 != (b & (1 << j))) {
                final int loc = P[i * 8 + j];
                result[loc / 8] |= (1 << (loc % 8));
            }
        }
    }
    return result;
}