Warning: Highly Geeky material follows.
I’m currently working on a large database for a customer. I’m actually redoing a crappy version of the database into a normalized screaming machine. I ran into a problem recently in that some of the values are stored as bitmasks. I knew what a bitmask was, but generally regarded them as voodoo magic left to crazy C hackers. Until now. I contacted my voodoo crazy C hacker mentor, Jeremy Brand, and asked him how they worked.
Here’s a quick tutorial:
instead of counting 0, 1, 2, 3, 4, 5… you could with powers of 2
instead 2^0, 2^1, 2^2, 2^3, 2^4, 2^5… (1, 2, 4, 8, 16, 32…).
When you lable something with one of these powers of two you can
add them to other powers of 2 and then later on divide out what
you started with again.
For example:
apple = 4
orange = 2
banana = 1
———–
sum = 7
The sum of your identifiers is 7 (lets call this $sum).
So, later on you can check 7 to see what is in your basket:
does $sum mod 4 equal 0? (then there is no apple in the cart)
does $sum mod 2 equal 0? (then there is no orange in the cart)
does $sum mod 1 email 0? (then there is no banana in the cart)
Using bitmasks isn’t neccesarily easier to use, but it is fast.
It’s fast because computers already thing in bits. This example
is using 3 bit memory. Typically you’ll have 16 options (like I
have 3 here) because of the size of an integer. If you’re lucky
you’ll be using C or even mysql that can access all 32 bits of an
integer then you’ll have 32 options.
The reason why computers use base-2 to to begin with are because
with storage hardware there is really only two states: on and off.
The more single units that you can store ons and offs the more
storage the device can have.
FYI, you can use google for your calculator:
eg. http://www.google.com/search?q=7+mod+4.
Finally, that makes sense. I’m still completely lost on the actual math that goes into making this work (which irks me), but I did manage to get a proof-of-concept program working, which may help other bitmask deficient programmers out there:
<?php
// Copyright 2004 Joe Stump <joe@joestump.net>
// Public Domain
// Usage: php -q bitmask.php 1 4 32
// (any numeric argument will be evaluated - change to whatever)
echo "Valid bitmask values (up to 16): n";
for ($i = 1 ; $i < 16 ; ++$i) {
echo "2 ^ $i = ".pow(2,$i)."n";
}
echo "nn";
$bitmask = 0;
$values = array();
for ($i = 1 ; $i < count($argv) ; ++$i) {
if (is_numeric($argv[$i])) {
$bitmask += $argv[$i];
$values[] = $argv[$i];
}
}
echo "Bitmask Contains: ".implode(', ',$values)."n";
echo "Bitmask Total: ".$bitmask."n";
echo "nResults:n";
$arr = array(1,2,4,8,16,32);
for ($i = 0 ; $i < count($arr) ; ++$i) {
echo $arr[$i].': '.((($bitmask & $arr[$i]) == 0) ? 'FALSE' : 'TRUE')."n";
}
?>
The trick is the &. If the result is 0 (zero) then the single bitmask value is not present in the sum of the bitmask. I’m sure this has something with the fact that you cannot add any separate list of single bitmask values and get the same sum twice (ie. 1 + 2 + 4 = 7, 2 + 4 + 8 = 14). Again, I just know “it works[tm]”. I hope this helps someone else out there.
I’m mainly caching this here so the next time my retarded mind can’t wrap itself around bitmasks I can check back to my own site. If you have questions concerning this don’t email me because I still think little green men make this mathematic “trick” work. Damn, I wish I had gotten a Computer Science degree instead of a Computer Info. Sys. degree.
