This is only of interest to programmers, but I ran across this technique and thought it was nifty. I was trying to compute all the possible subsets (of any size) of a given set. For example, given the set with three members:

{a,b,c}

the possible subsets are:

{}, the null set {a}, {b}, {c}, the sets with one member {a,b}, {a,c}, {b,c}, the sets with two members {a,b,c}, the sets with three members

Note that the sets are unordered, so {b,a} would be the same as {a,b}.

Now, the number these sets that exist can be pretty large — for a set of size n, the number of (unordered) subsets of size m is given by:

n!/(m!*(n-m)!)

So, the total number of subsets is given by:

sum for m=0 to n(n!/(m!*(n-m)!))

Most of the time we don't want to compute every possible subset, because this number gets very large very fast, but in case we do, here's the trick: bitmasks. If we have the previous set of three members, then we use a three-bit mask, where a one indicates that the member is in the subset, and a zero indicates it is not. Here's the representation of the above subsets:

{}=000 {a}=100, {b}=010, {c}=001 {a,b}=110, {a,c}=101, {b,c}=011 {a,b,c}=111

Why is this useful? Notice that every possible configuration of the bitmask has been used. If we looked at that as a binary number, it covers every value from zero (000) to seven (111). To test each subset of a given set of n members, create a counter whose maximum value is (2^n)-1, and increment from zero to this number. At each step, you can run some test on the subset indicated by that bitmask. Neat, huh?