I went down a few algorithmic roads recently, digging into path finding and – for some obscure reasons – bit manipulations. Or byte. Whatever.
Along this way some utility methods (or functions) were born, and I thought: May be some day some of them may be in use to any of you ;)
For my dear non-geeky readers: A bit is the smallest part in software. It’s either this or that, either 0 or 1, either false or true. With a group of 2 bits you already have 4 states: 00, 01, 10 and 11. With 8 it’s 256 and so on (2^n).
As it would be too boring to just type 0 or 1, and because we have more than 2 fingers, man invented numbers to accumulate these bits: so 9 stands for 1001, and because 9 is shorter than 1001, we prefer 9. Some even write AB for 10101011, but that’s where we come back to geeky world.
So after this highly informative introduction, let’s get to some code. First, let’s count bits:
static public function countBits( value : uint ) : uint { var count:uint = 0; while (value) { if ( value & 1 ) { count++; } value >>>= 1; } return count; }
Example:
countBits( 0xAB ) -> 5
Now sometimes you might wanna know: Does this data contain no more than 1 bit? We could just ask countBits( value ) == 1. But that’s not as speedy as it should be, right? So here we go:
static public function is_1_bit( value : uint ) : Boolean { var count:uint = 0; while (value) { if ( value & 1 ) { if (count == 1) return false; count++; } value >>>= 1; } return count == 1; }
Examples:
is_1_bit( 0xAB ) -> false
is_1_bit( 0×400 ) -> true
uint are by the way 32bit data, so a maximum of 32 of these bits we’re talking about can be turned on or off. That’s a lot of data. 4′294′967′296 combinations (though not that high compared to the numbers we read every day in the newspapers recently). Anyway, sometimes we might wanna access and set only a group of bits (usually 4 or 8) within this quite large row of bits:
static public function getBitGroup( value : uint , group : uint , len : uint = 4 ) : uint { return ( value >> (group*len) ) % (1 << len); } static public function setBitGroup( value : uint , groupValue :uint , group : uint , len : uint = 4 ) : uint { var pos:uint = group * len; var mask:uint = n_bits(pos); var right_bits:uint = value & mask; value >>>= pos + len; value <<= len; value |= groupValue; value <<= pos; value |= right_bits; return value; }
Don’t they look just groovy?! Yeah baby!
Anyway, that’s all for now. Stay tuned for some crazy path finding. If I find time (sometimes I wonder how all those bloggers find their time to write so much..) Not to mention Twitter. Boohaa.
