Packing numbers efficiently

I have n numbers in the range of 0..m-1. m doen't have to be a power of 2.

The most efficient way to pack them into a stream of bytes will require exactly log2(m)*n bits rounded up.

I get the numbers as a List<int> and m as int m. How can I pack it into List<byte> not exceeding the size of log2(m)*n/8?

After the 开发者_如何学Gopacking is done how can get the numbers back having the List<byte> and int n, m?

Homework?

Generally speaking, when you have N numbers in 0..M-1 range, this means that you have ONE number in 0..M*N-1 range. Representing this requires equal or fewer bits, log2(M*N), then the case when the numbers are encoded separately.

Next, if you know something else about the numbers (their distribution, or their dependency on one another), you can try to apply various compressing schemas. When the distribution is know, Huffman or similar encodings might be the simplest approach. When the sequential dependency is known, LZ(W) or similar would be the approach. And so on.

EDIT: answering the question in comment about how to store/write/read such a number. You can store the number in various forms. Byte arrays seem to be one (if not the) most efficient way to do so. Here's a quick example on how to do that using BigInteger, which is close enough to memory efficiency of the byte array, but with some convenient operations on top. You may want to re-write this using more appropriate storage:

int[] Ms = new int[] { 10, 11, 12, 13 };
int N = 42;
System.Numerics.BigInteger x = new System.Numerics.BigInteger();

System.Numerics.BigInteger power = 1;

// composing the pack:
foreach (int s in Ms) {
    x += power * s;
    power *= N;
}

// reading the pack:
//  extracting i'th number:
int i = 2;
power = System.Numerics.BigInteger.Pow(N, i);
int result = (int)((x / power) % N);

Treat the list of numbers as the digits of a base-m number.