So about those 32 booleans in a single integer…
An example i like to use is when you want to use a single value to represent the state of an object. Say for instance you’re describing a person. This person can have a series of traits. He can be happy, sad, tall, dead, asleep, hopeful.. Whatever. Let’s imagine this person as an object.
happy:true,
sad:false,
dead:false,
asleep:true
};
The problem becomes; from a collection of people, how do you pick out the ones that are happy and asleep?
{
var p:Object = a[i];
if (p.happy && p.asleep) {
trace("Got one!");
}
}
This is all relatively well and good, until you need a generic method to validate an arbitrary number of arguments.
for (var j:int = flags.length; j--; )
{
if (!o[flags[j]]) return false;
}
return true;
}
Using this while iterating over all your objects results in an obscene amount of overhead.
Enter bit-flagging.
Bit flagging requires the use of another three bitwise operators, known as the bitwise OR, the bitwise AND and the bitwise NOT. NOT simply takes a set of bits and sets them to their opposite (so 1 becomes 0). OR and AND are operators that take two integers and compare their bits to create new integers. It’s crazy! Let’s look at how they work.
ActionScript 3 bitwise OR, AND
int3 = int1 & int2; //AND
int3 = ~int1; //NOT
OR works as an all-pass gate, where if bit X in int1 is 1, OR bit X in int2 is 1, bit X in int3 is also 1.
0001 0000 =
0001 0001
This basically means that if there is a 1 in either of the two inputs, the result will have a 1 in those places as well.
Bitwise AND on the other hand, will only set a 1 if BOTH the inputs have a 1 in that position.
0001 0000 =
0000 0000
1000 0001 AND
1001 0000 =
1000 0000
Looking at this, it becomes clear that if we want to set a bit in an int, we have to OR the original value with a value where the target bit is set to 1. Backwards, if we want to check if a bit is set in a number, we AND the containing value with a number containing the target bit. What if we want to unset a bit?
= 1111 1110
With a little hot AND on NOT action we can inverse a collection of flags and return a new int that only contains the ones we want.
flagToUnset = 0000 0001
NOT flagToUnset = 1111 1110
state AND (NOT flagToUnset) = 0000 1000
Let’s say we’re making a game. Our game character can have several states. He can be jumping, running, punching, etc. We’ll declare these states as constant uints in our character class.
private const RUNNING:uint = 2;
private const PUNCHING:uint = 4;
private const DUCKING:uint = 8;
private const HURTING:uint = 16;
private var state:uint = 0;
Notice the pattern? We are associating every state with a value represented by a single bit in our state. Currently, the character is just standing around doing nothing, so his state is simply 0. But what now! He runs ahead!
Using OR, we have made sure that the bit in state representing the number associated with the RUNNING state is set to 1. But what now! His foot hits a banana peel! Is he still running?
slip();
}
Using AND, we have grabbed a new int that only contains the bits shared by the state and the RUNNING state, and compared that to the RUNNING state. What do you know, he’s running! The slip method sends him flying, and sets his state to JUMPING. In mid-air, he spots himself being on the way to hit an enemy, and stands a chance of being hurt. Unless of course he’s doing a RUNNING, JUMPING PUNCH! The ultimate sort of punch.
if(state & test == test){
//The ultimate sort of punch.
}
Ah-ha! So all those previous times we ANDed state with state value, those bits still stay set throughout, and by ANDing those state values together, we can create a new value with which to compare.
0000 0001 //JUMPING
0000 0100 //PUNCHING
//ANDed together makes
0000 0111 //7
state & 7 //7
As our character hits the ground he continues to triumphantly punch the air, but is no longer jumping or running.
Significance
Bit-flagging is significant for real-time applications where performance is a concern, such as in a game update loop, but are invaluable for any situation where you want to validate a range of booleans in as few operations as possible. Bitwise operations are lightning fast.
The techniques described in this post can be generically implemented using the following methods.
state|=newFlags;
}
function unSetFlags(flagsToUnset:uint):void{
state&=(~flagsToUnset);
}
function validateFlags(flagsToValidate:uint):Boolean{
return (state&flagsToValidate)==flagsToValidate;
}
Bitwise operators also have many other uses beyond that.
Of course :-) this is just a quick primer