🚀 go-pugleaf

Herman Rubin:
   >> Consider the following two operations, ...
   >> 1.  Examine a bit, ...
   >> 2.  Find the distance to the next one in a bit stream.

Terry Ingoldsby:
   >I have got to ask.  Why is it so generally important that the
   >distance between bits can be determined efficiently.

David Wright:
   Hear hear.  And this leads to a second question of HR, which has been
   posed once before but not answered (or I missed it):  Why does your
   application have to work on a bit stream? 

Chip Salzenberg:
   That kind of problem is not "generally important" in that it does not
   come up in the "general computing base".

harumph.

At work we have a hand-optimized assembly routine to convert from a
bit array to a list of indices.  It gets used a lot.

Please note that a bit list is very handy for dealing with selection
problems.  They are very compact, and have very predictable size
requirements.  Selection problems include highlighting text for
emphasis, intermediate results during a database query, as well as Herman
Rubin's probabalistic models.

They're also handy in some domains for converting from some arbitrary
list of integers to a unique, sorted list (but otherwise the same
integers), in O(n).

We use "bit lists as integers" for other things too (once you have a
generic feature you tend to use it whenever it's handy -- particularly
if it's fast).

As for the problem of "distance between bits" vs "absolute position of
bits" note that if you have a _lot_ of bits you start talking about
very long lists of integers (and possibly even exceeding maxint, or
whatever for the representation you're using).  This is particularly
painful if your bitlist is dense.  Both have their uses (as does
a list ordered pairs of the form (position, offset)), and we happen to
use them a lot.

Raul Rockwell