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.