Maybe you can share a bit about how the numbers between 1 and 100 are distributed, or some more properties of them? In general, it's impossible to encode an arbitrary subset of the numbers 1 to 100 in less than 100 bits.

yea , after posting the question it kind of hit me too. I recall from information theory that something like this is maybe not possible. some other information that i can give to you is : the numbers are always ordered (from smallest to largers). numbers are uniformly distributed and usually there are about 50 numbers in the array.

ps is it possible maybe to tahe only first 8 bits for numbers 1-8 and then use the generated bit-string as a key for encoding next 8 bits and then repeate this recursivly ... hm ... i cannot see it ....

Hashing is used to summarize content. There's no guarantee that collisions won't happen if the hashing algorithm creates a hash of fewer bits than the maximum possible entropy in the data set. And for your purposes, you are virtually assured of having collisions. As corion mentioned, you cannot uniquely represent the state of every number between 1 and 100 with fewer than 100 bits (your bit string approach is already an optimal solution if you cannot tolerate information loss). If you use a hashing solution instead, you will have collisions, since 16 bits is an inadequate key size to avoid collisions.

Can you tolerate collisions? Could you solve the problem that motivated this quest by taking a different route entirely (In other words, could this be an X-Y problem?)?

If subset size were known, you'd be counting the combinations.

for my $n (100) {
  for my $m (1..100) {
    my $i = 1;
    $i *= ($n+1-$_)/$_ for 1..$m;
    printf "C($m,$n) = $i (%.3f bits)\n", log($i)/log(2);
  }
}
[download]