Consider a storing a permutation of 2^8 = 256 elements. The easiest way to store it is a byte array of length 256, consuming 8*256 = 2048 bits total.
The densest possible encoding is mixed radix based on the factorial, requiring log(256!)/log(2) = 1683.996 bits. (The .996 is a nice coincidence.)
A hybrid approach does bit-packing. The first 128 elements use 8 bits per element, then the next 64 use 7 bits, and so forth. sum(i=0,7,2^i*(i+1)) = 1793 bits.
No comments :
Post a Comment