The Joel on Software Discussion Group (CLOSED)

A place to discuss Joel on Software. Now closed.

This community works best when people use their real names. Please register for a free account.

Other Groups:
Joel on Software
Business of Software
Design of Software (CLOSED)
.NET Questions (CLOSED)
TechInterview.org
CityDesk
FogBugz
Fog Creek Copilot


The Old Forum


Your hosts:
Albert D. Kallal
Li-Fan Chen
Stephen Jones

bitmask for tri-state values

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?
Jason Send private email
Tuesday, September 13, 2005
 
 
No.
Mr. Analogy {uISV} Send private email
Tuesday, September 13, 2005
 
 
Use two bits per value?
Game programmer
Tuesday, September 13, 2005
 
 
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).
redeye Send private email
Tuesday, September 13, 2005
 
 
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.
redeye Send private email
Tuesday, September 13, 2005
 
 
How about using trinary base system?
Berislav Lopac Send private email
Tuesday, September 13, 2005
 
 
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.
Mike Schiraldi
Tuesday, September 13, 2005
 
 
Programmers are expensive. Do whatever allows the programmers to think as little as possible and get their work done as quickly as possible.
Mike Schiraldi
Tuesday, September 13, 2005
 
 
And store that on a disk how?
Aaron F Stanton Send private email
Tuesday, September 13, 2005
 
 
Before I answer this question, which of the Five Worlds are you in?

http://www.joelonsoftware.com/articles/FiveWorlds.html
Robby Slaughter Send private email
Tuesday, September 13, 2005
 
 
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]));
}
Mike Schiraldi
Tuesday, September 13, 2005
 
 
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.
Aaron F Stanton Send private email
Tuesday, September 13, 2005
 
 
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...)
Mark Bessey Send private email
Tuesday, September 13, 2005
 
 
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.
Mark Bessey Send private email
Tuesday, September 13, 2005
 
 
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 };
Chris Nahr Send private email
Wednesday, September 14, 2005
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz