https://hugmanrique.me/posts/thinking-in-bits/

CompactedArray.java

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkElementIndex;
import static com.google.common.base.Preconditions.checkNotNull;

import java.util.Arrays;
import javax.annotation.concurrent.NotThreadSafe;

/**
 * A long array that holds a fixed number of {@code ints} of a certain bit length.
 */
@NotThreadSafe
public final class CompactedArray {

    private static final int LONG_BITS = Long.BYTES * 8;
    // Position of 1 bit in LONG_BITS (which is always a power of 2)
    private static final int LONG_DIV_SHIFT = MathHelper.log2(LONG_BITS);
    private static final int LONG_MOD_MASK = LONG_BITS - 1;

    private static int getRawLengthFor(final int length, final int bitsPerInt) {
        // See Appendix 1 for ceilDiv implementation
        return MathHelper.ceilDiv(length * bitsPerInt, LONG_BITS);
    }

    private final long[] data;

    private final int length;
    private final int bitsPerValue;
    private final long bitmask;

    /**
     * Constructs an array that holds {@code length} integers with {@code bitsPerValue} bits each.
     *
     * @param length the number of values
     * @param bitsPerValue the bit-length of each value
     */
    public CompactedArray(final int length, final int bitsPerValue) {
        this(length, bitsPerValue, new long[getRawLengthFor(length, bitsPerValue)]);
    }

    /**
     * Constructs an array that holds {@code length} integers with {@code bitsPerValue} bits each
     * backed by the specified array.
     *
     * @param length the number of values
     * @param bitsPerValue the bit-length of each value
     * @param data the array by which this {@link CompactedArray} will be backed
     * @throws IllegalArgumentException if the array length is invalid
     */
    public CompactedArray(final int length, final int bitsPerValue, final long[] data) {
        this.data = checkNotNull(data, "packed");
        // TODO Implement checkNonNegative
        this.length = checkNonNegative(length, "length");
        this.bitsPerValue = checkNonNegative(bitsPerValue, "bitsPerInt");
        this.bitmask = (1L << bitsPerValue) - 1; // e.g. bitsPerInt = 5 => bitmask = 0b11111
        checkArgument(data.length == getRawLengthFor(length, bitsPerValue),
                "Invalid array length {} for {}", data.length, this);
    }

    // Division by LONG_BITS is equivalent to shifting by LONG_DIV_SHIFT.
    // Modulo LONG_BITS is equivalent to AND with LONG_MOD_MASK.

    /**
     * Returns the element at the specified position.
     *
     * @param index the index of the element to return
     * @return the element at the specified position
     * @throws IndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= length()})
     */
    public int get(final int index) {
        int bitOffset = checkElementIndex(index, length) * bitsPerValue;
        int offset = bitOffset >> LONG_DIV_SHIFT;
        int startBit = bitOffset & LONG_MOD_MASK;
        int nextOffset = (bitOffset + bitsPerValue - 1) >> LONG_DIV_SHIFT;

        long value = (data[offset] >>> startBit) & bitmask;

        if (offset != nextOffset) {
            int shiftBy = 64 - startBit;
            value |= (data[nextOffset] << shiftBy) & bitmask;
        }

        return (int) value;
    }

    /**
     * Replaces the element at the specified position with the given element.
     *
     * @param index the index of the element to replace
     * @param value the new element
     * @throws IndexOutOfBoundsException if index is out of range
     *         ({@code index < 0 || index >= length()})
     */
    public void set(final int index, final int value) {
        int bitOffset = checkElementIndex(index, length) * bitsPerValue;
        int offset = bitOffset >> LONG_DIV_SHIFT;
        int startBit = bitOffset & LONG_MOD_MASK;
        int nextOffset = (bitOffset + bitsPerValue - 1) >> LONG_DIV_SHIFT;
        long maskedValue = value & bitmask;

        data[offset] = (data[offset] & ~(bitmask << startBit)) | (maskedValue << startBit);

        if (offset != nextOffset) {
            int shiftBy = 64 - startBit;
            data[nextOffset] =
                    (data[nextOffset] >>> shiftBy << shiftBy) | (maskedValue >> shiftBy);
        }
    }

    /**
     * Returns the fixed number of elements this array holds.
     *
     * @return the number of element this array holds
     */
    public int length() {
        return length;
    }

    /**
     * Gets the backing array of {@code longs}.
     *
     * @return the array by which this {@link CompactedArray} is backed
     */
    public long[] data() {
        return data;
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(data);
    }

    @Override
    public boolean equals(Object that) {
        return this == that || (that instanceof CompactedArray
                                && Arrays.equals(data, ((CompactedArray) that).data));
    }
}

CompactedArrayTests.java

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.Test;

public class CompactedArrayTests {

    @Test
    void testGet() {
        long[] data = { 0x123456789ABCDEF0L, 0xABCDEF0123456789L};
        CompactedArray array = new CompactedArray(14, 9, data);

        assertEquals(0b011110000, array.get(0));
        assertEquals(0b010101111, array.get(2));
        assertEquals(0b100010010, array.get(7));
        assertEquals(0b001001000, array.get(10));
    }

    @Test
    void testSetAndGet() {
        CompactedArray array = new CompactedArray(20, 7);

        array.set(0, 0b1011001);
        assertEquals(0b1011001, array.get(0));
        assertEquals(0, array.get(1));
        array.set(9, 0b0110110);
        assertEquals(0b0110110, array.get(9));
        assertEquals(0, array.get(8));
        assertEquals(0, array.get(10));
        array.set(12, 0b0001001);
        assertEquals(0b0001001, array.get(12));
        assertEquals(0, array.get(11));
        assertEquals(0, array.get(13));
        array.set(19, 0b1101011);
        assertEquals(0b1101011, array.get(19));
        assertEquals(0, array.get(18));
    }

    @Test
    void testLengthValidation() {
        assertThrows(IllegalArgumentException.class, () -> {
            long[] data = new long[0]; // Too small
            new CompactedArray(2, 4, data);
        });

        assertThrows(IllegalArgumentException.class, () -> {
            long[] data = new long[2]; // Too big, can hold 14 words
            new CompactedArray(6, 9, data);
        });

        assertThrows(IllegalArgumentException.class, () -> {
            long[] data = new long[5]; // Too small, can hold 320 words
            new CompactedArray(21, 20, data);
        });
    }

    @Test
    void testOutOfBounds() {
        CompactedArray array = new CompactedArray(20, 7);

        assertThrows(IndexOutOfBoundsException.class, () -> array.get(-2));
        assertThrows(IndexOutOfBoundsException.class, () -> array.get(20));
        assertThrows(IndexOutOfBoundsException.class, () -> array.get(451));
        assertThrows(IndexOutOfBoundsException.class, () -> array.set(-1, 3));
        assertThrows(IndexOutOfBoundsException.class, () -> array.set(20, 21));
        assertThrows(IndexOutOfBoundsException.class, () -> array.set(598, 43));
    }

    @Test
    void testEquality() {
        long[] data = new long[1];

        CompactedArray numbers = new CompactedArray(4, 9, data);
        CompactedArray sameNumbers = new CompactedArray(4, 9, data);

        // Mutate backing array
        numbers.set(1, 15);

        assertEquals(numbers, sameNumbers);
        assertEquals(sameNumbers, numbers);
        assertEquals(numbers.get(1), sameNumbers.get(1));
    }
}

LICENSE

MIT License

Copyright (c) 2020 Hugo Manrique

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.