## Tuesday, June 9, 2009

### Power Set of a Bitmask

Here’s a cute trick for enumerating the power set of an integer bitmask. It’s based on equation (84) in Donald Knuth’s The Art of Computer Programming, Volume 4, pre-fascicle 1A, page 18, available in an "alpha test" version at:

http://www-cs-faculty.stanford.edu/~knuth/taocp.html

The idea is that, given a subset (x) of a mask (M) the next largest lexicographic subset (x') is:

x’ = (x – M) & M

Combined with the C# "yield return" statement, this allows a simple enumeration of the power set of a mask. You simply seed the subset with zero, and iterate until it is once again zero.

``public static IEnumerable<int> PowerSet (  int maskIn){  int xSet = 0;        do   {    yield return xSet;    xSet = (xSet - maskIn) & maskIn;  }   while (xSet!=0);}``

For example, calling PowerSet(0x19) returns an enumerator which yields (in binary):

00000
00001
01000
01001
10000
10001
11000
11001

I can’t think of a specific use for it right off hand, but if a project uses enough bit manipulation, I’m sure something would arise.