## 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 |
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?
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.
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
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])); }
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.
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. |

Powered by FogBugz