Java - оптимизирует запись значений как битов в байтовый буфер

Ответ 1

Хорошо, я изменил ваш оригинальный алгоритм, чтобы удалить часть избыточной математики, и я побрил около 10% (от 0,016 мс до 0,014 мс на моей машине). Я также изменил свой тест, чтобы запустить каждый алгоритм 1000 раз.

Также существует некоторая экономия, которая должна быть получена в последнем цикле for, поскольку одни и те же биты перемещаются снова и снова. Если бы вы могли как-то сохранить результаты предыдущей смены, которые могли бы помочь. Но это изменило бы порядок байтов, и это потребовало бы еще нескольких размышлений.

public void writeBits3(long value, int amount) {
    if (bitIndex != 0) {
        int remainingBits = 8 - bitIndex;
        int bytePos = out.position() - 1;
        byte current = out.get(bytePos);
        int shiftAmount = amount - remainingBits;

        int bitsWritten = 0;
        if (shiftAmount < 0) {
            bitsWritten = amount;
            out.put(bytePos, (byte) (current | (value << -shiftAmount)));
        } else {
            bitsWritten = remainingBits;
            out.put(bytePos, (byte) (current | (value >> shiftAmount)));
        }

        bitIndex += bitsWritten;
        amount -= bitsWritten;
        if (bitIndex >= 8) {
            bitIndex = 0;
        }
    }
    if (amount <= 0) {
        return;
    }
    bitIndex = amount & 7;
    int newAmount = amount - bitIndex;
    long newValue = (value >> bitIndex);
    for (; newAmount >= 8; newAmount -= 8) {
        out.put((byte) (newValue >> newAmount));
    }
    out.put((byte) (value << (8 - bitIndex)));
}

Ответ 2

Здесь лучшее решение (чем мое предыдущее), использующее рекурсию, которая идеально подходит для этой проблемы.

private static final long[] mask = { 0, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff };

private ByteBuffer out = ByteBuffer.allocate(1024);
private int position = 0;
private int dataBits = 0;
private byte remainder = 0;

/**
 * value: The value to write
 * amount: The number of bits to represent the value in.
 */
public void writeBits(long value, int amount) {
    if (amount <= Long.SIZE) {
        if (amount > 0) {
            // left align the bits in value
            writeBitsLeft(value << (Long.SIZE - amount), amount);
        } else {
            // flush what left
            out.put(position++, remainder);
        }
    } else {
        // the data provided is invalid
        throw new IllegalArgumentException("the amount of bits to write is out of range");
    }
}

/**
 * write amount bits from the given value
 * 
 * @param value represents bits aligned to the left of a long
 * @param amount bits left to be written from value
 */
private void writeBitsLeft(long value, int amount) {
    if (amount > 0) {
        // how many bits are left to be filled in the current byte?
        int room = Byte.SIZE - dataBits;

        // how many bits are we going to add to the current byte?
        int taken = Math.min(amount, room);

        // rotate those number of bits into the rightmost position
        long temp = Long.rotateLeft(value, taken);

        // add count taken to the count of bits in the current byte
        dataBits += taken;

        // add in that number of data bits
        remainder &= temp & mask[taken];

        // have we filled the byte yet?
        if (Byte.SIZE == dataBits) {
            out.put(position++, remainder);

            // reset the current byte
            remainder = 0;
            dataBits = 0;

            // process any bits left over
            writeBitsLeft(temp, amount - taken);
        }
    } 
} // writeBitsLeft()

Это решение имеет меньше математических операций, меньше операций смены и меньше операторов if и поэтому должно быть более эффективным, чем исходное решение, не говоря уже о том, что это может быть немного легче понять.

Ответ 3

Как насчет этого?

private ByteBuffer out = ByteBuffer.allocate(1024);
private int position = 0;
private int dataBits = 0;
private long data = 0;

/**
 * value: The value to write
 * amount: The number of bits to represent the value in.
 */
public void writeBits(long value, int amount) {
    if (amount <= 0) {
        // need to flush what left
        if (dataBits > 0) {
            dataBits = Byte.SIZE;
        }
    } else {
        int totalBits = dataBits + amount;

        // need to handle overflow?
        if (totalBits > Long.SIZE) {
            // the new data is to big for the room that remains;  by how much?
            int excess = totalBits - Long.SIZE;

            // drop off the excess and write what left
            writeBits(value >> excess, amount - excess);

            // now we can continue processing just the rightmost excess bits
            amount = excess;
        }

        // push the bits we're interested in all the way to the left of the long
        long temp = value << (Long.SIZE - amount);

        // make room for any existing (leftover) data bits, filling with zeros to the left (important)
        temp = temp >> dataBits;

        // append the new data to the existing
        data |= temp;

        // account for new bits of data
        dataBits += amount;
    }

    while (dataBits >= Byte.SIZE) {
        // shift one byte left, rotating the byte that falls off into the rightmost byte
        data = Long.rotateLeft(data, Byte.SIZE);

        // add the rightmost byte to the buffer
        out.put(position++, (byte)(data & 0xff));

        // drop off the rightmost byte
        data &= 0xffffffffffffff00L;

        // setup for next byte
        dataBits -= Byte.SIZE;
    }
}