Re: RBB: Really Big Bitvectors

From: Paul Cole (
Date: 12/09/95

On Fri, 8 Dec 1995, Kenneth G. Cavness wrote:

> The irritant is that I'm almost certain there will _have_ to be more than 
> one byte used. However, even if you were to have 55 flags in a 32-bit 
> longint, it would be a 23-flag improvement.

Huh?  Could you post your theory again?  I really don't think you can get 
more than one flag per bit into a variable <8 bit, 16bit, or 32 bit> no 
matter what mathematics you use to massage it with.  However, you could
use logic to massage a value into holding more than numbit FLAGS but they 
would have to be mutually exclusive flags.

Here's a little discussion on the subject thrown together on the fly:

FLAG -- a STATE <example of uses in *mud, FLYING, 
BITVECTOR -- a variable which can repreresent one or more FLAGS or STATES.

An 8 bit field can represent only 8 states or flags normally.  No 
amount of mathematic massaging is going to change that.  Adding primes 
won't work nor any other method besides adding factors of 2.  A previous 
post summed up the problem with those approaches stating that a sum of 2 
primes is often larger than the value the field can hold.  That isn't 
true.  The problem is that you can't decode a sum of primes back into its 
original parts.

For example, take the simplest case:
  suppose an 8 bit field holds 9 flags:
   FLAG1 = 1
   FLAG2 = 2
   FLAG3 = 3
   FLAG4 = 5
   FLAG5 = 7
   FLAG6 = 11
   FLAG7 = 13
   FLAG8 = 17
   FLAG9 = 19
Now its obvious that the field can hold one of these flags and the result 
is easily distinguishable. However, what about the case when we have 2 
flags set?  Suppose FLAG9 and FLAG3 and FLAG2 are set... field in that case 
would be 19+3+2 = 24.  During decode what do you get? It could be 
FLAG6+FLAG7 = 24!  Wrong answer!

Only a sum of factors of 2 will work this way.  And guess what factors of 
2 are..  They are equivalent to bits

1 = 1<<0
2 = 1<<1
4 = 1<<2
Now for the method that does work but is highly proprietary.

You can encode your bitfield such that part of the bitfield is a key for 
the meanings of the remaining bits.

For example
Suppose you have 4 bits you want to represent SWIMMING, DIVING, 
                                              WALKING,  RUNNING

Normal straight forward method would be to use 4 bits to control these 
flags or states.  

SDWR <1000 is swimming, 0001 is running>

But close inspection would show that you can use a mere 2 bits for these 4
values becuase RUNNING is only possible when you are WALKING and DIVING is
only possible when you are SWIMMING. Also, I note that WALKING is the same
thing as NOT FLYING. So you could <though I don't, too much work> use 2
bits to represent this. 

XY where
    X -- 1 = SWIMMING, 0 = WALKING
    Y -- 1 = DIVING,   0 = RUNNING
   10 = SWIMMING     and NOT DIVING
   11 = SWIMMING     and DIVING

Thus I've just implemented all 4 STATES in 2 BITS.

This is very proprietary and imho, not terribly useful.  It is only 
presented here as a method for representing more than X FLAGS in an Xbit 
bit field.

  --Paul Cole
  stil @ forbidden lands < 5000>

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