Encoding small numbers to bytes-CodePudding

I am looking for the most efficient way to store array of small numbers 0-31 (exactly 5 bits each) and decode them back in C#. Should I use array of bytes or some bitarray? How to encode and decode it with minimum overhead? Input can be List of bytes where each byte has maximum value 31 (5 bits used only), so 8 numbers should be encoded to 5 bytes.

CodePudding user response：

You could use something like this:

class SmallIntArray
{
    const uint BitsPerInt = 5;

    private BitArray[] b;

    public SmallIntArray(int len)
    {
        b = new BitArray[BitsPerInt];

        for (int pos = 0; pos < BitsPerInt; pos  )
        {
            b[pos] = new BitArray(len);
        }
    }

    public int this[int idx]
    {
        get
        {
            int res = 0;

            checkIndex(idx);
            for (int pos = 0; pos < BitsPerInt; pos  )
            {
                res = (res << 1)   (b[pos].Get(idx) ? 1 : 0);
            }
                            
            return res;

        }

        set
        {
            int i = value;

            checkIndex(idx);
            for (int pos = 0; pos < BitsPerInt; pos  )
            {
                b[pos].Set(idx, (i & 1) == 1);
                i >>= 1;
            }

            //  catch arguments with too many bits
            Debug.Assert(i == 0);
        }
    }

    private void checkIndex(int idx)
    {
        Debug.Assert((idx >= 0) && (idx < b.GetLength(0)));
    }
}

Example usage:

 var sia = new SmallIntArray((int)10e6);

 sia[1234] = 17;

 Console.WriteLine($"{sia[1234]}");

The measured memory consumption is near 5 bits per number.

CodePudding user response：

You could use a fairly simple unrolled loop, along with some bit-twiddling, to convert between these two formats.

I've assumed the arrays are exactly divisible by 8 and 5, otherwise you will need to devise a method to store the length.

public byte[] ConvertTo5Bit(byte[] array)
{
    Debug.Assert(array.Length % 8 == 0);
    var length = array.Length / 8 * 5;
    var newArray = new byte[length];
    for (var i = 0; i < array.Length; i  = 8)
    {
        newArray[i] = array[i] | (array[i   1] << 5);
        newArray[i   1] = (array[i   1] >> 3) | (array[i   2] << 2) | (array[i   3] << 7);
        newArray[i   2] = (array[i   3] >> 1) | (array[i   4] << 4);
        newArray[i   3] = (array[i   4] >> 4) | (array[i   5] << 1) | (array[i   6] << 6;
        newArray[i   4] = (array[i   6] >> 2) | (array[i   7] << 3);
    }
    return newArray;
}

public byte[] ConvertFrom5Bit(byte[] array)
{
    Debug.Assert(array.Length % 5 == 0);
    var length = array.Length / 5 * 8;
    var newArray = new byte[length];
    for (var i = 0; i < array.Length; i  = 5)
    {
        newArray[i] = array[i] & 0x1F;
        newArray[i   1] = (array[i] >> 5) | (array[i   1] << 3) & 0x1F
        newArray[i   2] = (array[i   1] >> 2) & 0x1F;
        newArray[i   3] = (array[i   1] >> 7) | (array[i   2] << 1) & 0x1F;
        newArray[i   4] = (array[i   2] >> 4) | (array[i   3] << 4) & 0x1F;
        newArray[i   5] = (array[i   3] >> 1) & 0x1F;
        newArray[i   6] = (array[i   3] >> 6) | (array[i   4] << 2 & 0x1F;
        newArray[i   7] = array[i   4] >> 3;
    }
    return newArray;
}