Sunny Walker's Blog

« Sequencer Tool | Main | No ke aha au e aʻo nei i ka ʻōlelo Hawaiʻi? »

September 09, 2009

I've forgotten my math

There's a great way for saving space in databases for flag fields by using bit-level math. That is, use binary operations to keep track of a variable number of flags and just store that in a single integer value in the database.

I'll clarify a little more. Rather than storing the following yes/no fields: is_active, is_done, is_pending_approval, is_on_hold, and is_canceled, simply assign a bit value to each one and store that as an integer.

is_active           =  1 (00001)
is_done             =  2 (00010)
is_pending_approval =  4 (00100)
is_on_hold          =  8 (01000)
is_canceled         = 16 (10000)

One integer field saves database space and provides for the ability to add more flags without having to modify the database structure. Simply add each flag value to generate the integer. Want to mark a record as active and on hold? 1 + 8 = 9. UPDATE tablename SET flags=(flags | 9) WHERE id=100;

It's easy to test against specific flags using bit-wise operations. Want to know which records are done? SELECT * FROM tablename WHERE (flags & 2);

The trick, however, is in validating the bit value for the lookup table for the flags. You only want to allow the values to be powers of 2. But how do you know if an arbitrary number entered is such a number? This is where I've forgotten my math.

It took a little bit of research but success is mine. Taking the base 2 logarithm (AKA log2(n) or lg(n) or log(n)/log(2)) calculates the power of 2. Then subtract that number from the floor() of itself will grab the remainder. If that remainder is 0, the number is a power of two.

In PHP, this looks like function isPowerOf2($n) { $x=log($n,2); return $x-floor($x)==0; }

Granted, it was a minor victory, but a victory none-the-less!

Posted at September 9, 2009 12:47 PM | Life and Work

Comments

Post a comment