Util 从字节数组中提取位到一个新的 byte[]

Question

我正在尝试构建一个实用程序类以使按位操作和转换更具可读性。目前我一直在构建一种方法来从字节数组中提取位并从中形成一个新的 byte[]。不用说我对按位运算不是很流利。我相信它可能可以使用 BitSet 来实现，但是会有太多的转换并且实现将是特定于 Java 的。如果有一个清晰的算法可以在以后轻松移植到其他语言，那就太好了。到目前为止，我已经做到了：    public static byte[] toBytes(int offset /*full bytes*/, int bitsOffset /*bytes + bits*/, int bitsCount, byte... bytes) {        int bytesCount = bitsCount / 8;        int paddingBits = bitsCount % 8;        int partialBits = 8 - paddingBits;        if (paddingBits > 0) {            bytesCount++;        }        byte[] data = new byte[bytesCount];        return data;    }我已经评论了上面的内容并将其临时替换为    public static byte[] toBytes(int offset, int bitsOffset, int bitsCount, byte... bytes) {        int firstBitIndex = (offset * 8) + bitsOffset;        return new BigInteger(new BigInteger(1, bytes).toString(2).substring(firstBitIndex, firstBitIndex + bitsCount), 2).toByteArray();    }但是我仍然希望有一个尽可能少的开销并且不特定于 Java 的正确实现（不使用特定于 Java 的工具，如 BitSet）这是我期望它做什么的暗示   /**     * [0000 0110   1111 0010] = toBytes(1, 4, 12, [xxxx xxxx   xxxx 0110   1111 0010   xxxx xxxx])     * [0000 0110   1111 0010] = toBytes(1, 5, 12, [xxxx xxxx   xxxx x011   0111 1001   0xxx xxxx])     * [0000 0110   1111 0010] = toBytes(1, 6, 12, [xxxx xxxx   xxxx xx01   1011 1100   10xx xxxx])     */

Answer 1

到目前为止，我已经 [...]byte[] data = new byte[bytesCount];

不幸的是，这种方法只有在您的位偏移量是 8 的倍数时才有效。在所有其他情况下，您必须划分要复制的每个字节。下图说明了如何划分每个字节以及将划分的部分放在哪里。

_{MSB = 最高有效位
LSB = 最低有效位}

由于有很多极端情况，实现上述算法有点棘手。以下实现通过了您的所有测试和我的所有测试。我使用了许多变量来为所有计算赋予有意义的名称，希望它更容易理解。您可以通过消除其中一些变量并就地计算一些值来缩短实施时间。

我冒昧地将您的功能重命名toBytes为bitSubstring. 对于已经将字节作为输入的方法，以前的名称toBytes似乎有点不合时宜。

public static byte[] bitSubstring(int byteOffset, int bitOffset,

                                  int lengthInBits, byte... source) {

    return bitSubstring(8 * byteOffset + bitOffset, lengthInBits, source);

}

public static byte[] bitSubstring(int startBit, int lengthInBits,

                                  byte... source) {

    assert startBit >= 0 && startBit < 8 * source.length;

    assert lengthInBits >= 0 && startBit + lengthInBits <= 8 * source.length;

    int lengthInBytes = (int) Math.ceil(lengthInBits / 8.0);

    byte[] target = new byte[lengthInBytes];

    int startByte = startBit / 8;

    int endBitExclusive = startBit + lengthInBits;

    int endByteExclusive = (int) Math.ceil(endBitExclusive / 8.0);

    int sourceBytesToRead = endByteExclusive - startByte;

    int lowerPartSize = 8 * endByteExclusive - endBitExclusive;

    int shiftLowerUp = (8 - lowerPartSize);

    int shiftUpperDown = lowerPartSize;

    int lastSrc = 0;

    if (sourceBytesToRead > lengthInBytes) {

        lastSrc = source[startByte] & 0xFF;

        startByte++;

    }

    for (int targetByte = 0; targetByte < target.length; ++targetByte) {

        int curSrc = source[startByte + targetByte] & 0xFF;

        target[targetByte] |= (lastSrc << shiftLowerUp)

                            | (curSrc >>> shiftUpperDown);

        lastSrc = curSrc;

    }

    int overhang = 8 * lengthInBytes - lengthInBits;

    if (overhang > 0) {

        target[0] &= 0xFF >>> overhang;

    }

    return target;

}

上面的算法应该相当快。但是，如果您只对实现大小和可读性感兴趣，那么逐位复制的方法会更好。

public static byte[] bitSubstringSlow(int startBitSource, int lengthInBits,

                                      byte... source) {

    byte[] target = new byte[(int) Math.ceil(lengthInBits / 8.0)];

    int startBitTarget = (8 - lengthInBits % 8) % 8;

    for (int i = 0; i < lengthInBits; ++i) {

        setBit(target, startBitTarget + i, getBit(source, startBitSource + i));

    }

    return target;

}

public static int getBit(byte[] source, int bitIdx) {

    return (source[bitIdx / 8] >>> (7 - bitIdx % 8)) & 1;

}

public static void setBit(byte[] target, int bitIdx, int bitValue) {

    int block = bitIdx / 8;

    int shift = 7 - bitIdx % 8;

    target[block] &= ~(1 << shift);

    target[block] |= bitValue << shift;

}

......或更少可重复使用但更短：

public static byte[] bitSubstringSlow2(int startBitSource, int lengthInBits,

                                       byte... source) {

    byte[] target = new byte[(int) Math.ceil(lengthInBits / 8.0)];

    int startBitTarget = (8 - lengthInBits % 8) % 8;

    for (int i = 0; i < lengthInBits; ++i) {

        int srcIdx = startBitSource + i;

        int tgtIdx = startBitTarget + i;

        target[tgtIdx / 8] |= ((source[srcIdx / 8] >>> (7 - srcIdx % 8)) & 1)

                              << (7 - tgtIdx % 8);

    }

    return target;

}