RBB: Really Big Bitvectors

From: Kenneth G. Cavness (stargoat@tic.com)
Date: 12/01/95

I've been contemplating finding a way to make an unsigned char (0-255) store
more than the usual 8 bitvectors.

No, I'm not talking about the char eg[1] kludge, I'm talking about a 
"sophisticated" system that allows, through the use of functions (if we 
were using C++, we could overload operators, but we ain't so it's moot),
operations like bitwise and, or, xor, ones-complement, etc to be usable 
on more than the actual 8 bits.

How to do this? Define operations that consider 0-255 each to be one bit.
adding and subtracting each number would give a different bitvector. So, 
you could conceivably have 256 combinable flags where you had 8 before, 
all stored on one byte.

Well, no such luck.

For example, it's easy to say "1 and 5 are now bits; and-them together."
You'd get "6". Now, at that point, YOU know that 1 and 5 are bits. The
computer, however, sees "6" as a bit too, so how can the computer 
differentiate between "1 & 5" and "6" ?

Well, after several futile tries, I've come up with some ideas, and maybe 
some of you can help flesh them out for me:

1. Have a 1-3 byte header that somehow denotes what number is what. Even
if you have a 32-bit RBB structure with 126-256+ "bits", it's better than
the original 32-bits you would get otherwise.

2. Have the RBB use only prime numbers. There is an easy algorithm to 
determine a number's prime eligibility and I'm not sure, but I think there
are more than the usual for each byte, and especially as you get higher
up into the numbers.

3. Have the RBB use each "bit" in multiples of some number that will allow
you to use the numbers BETWEEN each "bit" as a pointer that this "bit" has
been set. Would require a very elaborate algorithm.

Any other suggestions?

Kenneth G. Cavness                  |   http://ccwf.cc.utexas.edu/~cavness
Associate Editor                    |   "That which is possible is not always
MIDS, TIC                           |    probable." -- Isaac Asimov
1-512-451-7602                      |   "What about the Tuna?" -- Unknown

This archive was generated by hypermail 2b30 : 12/07/00 PST