The Joel on Software Discussion Group (CLOSED)

You can use a bitmask to encode a set of binary values into a single value, and then easily pull the individual values back out with some simple bitwise operations.

What if you want to do the same thing with a set of tri-state values?  Is there any similar, simple method that would work?

No.

Use two bits per value?

Or two sets of values where the values in the first set represent the first and second state and the second set represents whether the tri state is set or not (thus you could only have a 1 in the second set where the equivalent value in the first set was 1).

eg:

0 - no
1 - yes
2 - maybe

Option A - yes
Option B - no
Optopn C - no
Option D - maybe


D C B A
1 0 0 1  = 9 (first state)
1 0 0 0  = 8 (second state)

So you would store the values 9 and 8 seperately.

When it comes to decoding you first decode the (9) to see that Option A and Option D are chosen, then you decode the (8) to find that option D is in its tri-state.

How about using trinary base system?

Seriously, just use two bits per value. In fact, i'd just use an entire int for the value so i could do stuff like:

int bits[100];

#define NO 0
#define YES 1
#define MAYBE 2

bits[5] = YES;
state = bits[9];

RAM is cheap. Hard drives doubly so. Bandwidth is cheap too.

Programmers are expensive. Do whatever allows the programmers to think as little as possible and get their work done as quickly as possible.

And store that on a disk how?

Before I answer this question, which of the Five Worlds are you in?

http://www.joelonsoftware.com/articles/FiveWorlds.html

The usual way. ASCII is more programmer-friendly:

const char * prettify (int i) {
  if (i == 0) return "NO";
  if (i == 1) return "YES";
  if (i == 2) return "MAYBE";
  return "Huh?";
}

...

for (i = 0 ; i < MAX ; i++) {
  fprintf (fp, "%d\n", prettify (bits[i]));
}

So encode the trinary system.  Yes, I got that, but I'm confused as to how that makes for easy bit masking.

Obviously, I'm not in the right head space today.

Bit masking for 2-bit values is no harder than doing it for 1-bit values. The masks are different, of course.

If you have something like:

#define TWO_BIT_MASK 0x03 /* last two bits on*/
#define MASK_BIT_0_AND_1 (TWO_BIT_MASK)
#define MASK_BIT_2_AND_3 (TWO_BIT_MASK<<2)
#define MASK_BIT_4_AND_5 (TWO_BIT_MASK<<4)
#define MASK_BIT_6_AND_7 (TWO_BIT_MASK<<6)

That defines your basic two-bit masks for adjacent pairs of bits in a byte. Then you can do all the basic tricks:

int z=0x99;
int get_bits_two_and_three=(z & MASK_BIT_2_AND_3)>>2;
int set_two_and_three=(z | MASK_BIT_2_AND_3);
int reset_two_and_three=(z & (!MASK_BIT_2_AND_3);

(I'm sure I've screwed up at least one of the above. I should draw a diagram...)

I forgot to mention the (obvious?) point that two bits per value gives you four states, not three. For most applications, you can use the extra state as an invalid or "don't care" state.

If you really need to pack the maximum number of 3-state values into a given amount of memory, you could look into arithmetic coding, using a non-binary base. You can't use the bitwise operators then, but basic modular arithmetic serves, and isn't much slower in practice.

// This value is just
// floor(ln(2)/ln(3)*CHAR_BIT*sizeof(unsigned))
// which determines the number of tri-state bits that
// will fit into an unsigned int
#define TRITS_IN_UNSIGNED 20
static unsigned power_table[TRITS_IN_UNSIGNED]={
1, 3, 9, 27, 81,
243, 729, 2187, 6561, 19683,
59049, 177147, 531441, 1594323, 4782969,
14348907, 43046721, 129140163, 387420489, 1162261467
};

// could add some error checking, or rewrite as a macro
// for speed & convenience
unsigned get_trivalue(unsigned value, int digit) {
    // lop off unused top digits - you can skip this
    // for the most-significant digit
    if (digit < (TRITS_IN_UNSIGNED-1)) {
      value = value % power_table[digit+1];
    }
    // truncate lower digits
    value = value / power_table[digit];
    return value;
}

And yes, this obviously generalizes to any arbitrary number base, given that the bitwise logical operators are just arithmetic operators for base-2 numbers.

With C# 2.0 you can simply use built-in nullable booleans to store a ternary state, and a regular array to store a bunch of them:

bool?[] values = { true, false, null };