find set bits positions in a byte

Question

I was tyring to create a sparse octree implementation like the people at nVidia ("Efficient Sparse Voxel Octrees") were doing for their voxel things when I came across this issue:

I have a bitfield of type byte (so 8 bits only) that tells me where the leafs of the octree are (1 says leaf, 0 means no leaf, 8 nodes attached --> 8 bit). What I want to do now is returning an array of the leaf positions. My current implementation is using a while loop to find out if the LSB is set. The input is shifted by 1 afterwards. So here's how I do that:

int leafposition = _leafmask & _validmask;
int[] result = new int[8]; 
int arrayPosition = 0;
int iteration = 0;
while ( leafposition > 0 )
{
   iteration++; //nodes are not zero-indexed ... ?
   if ( (leafposition & 1) == 1 ) // LSB set?
   {
     result.SetValue( iteration, arrayPosition );
     arrayPosition++;
   };
   leafposition = leafposition >> 1;
}
return result;

This is not looking elegant and has two things that are disturbing:

• This while loop mimics a for loop
• the result array will most likely be smaller that 8 values, but resizing is costly

I expect the result to be like [2,4,6] for 42 (0010 1010).

Can anyone provide a more elegant solution that is still readable?

---

Result

I am using a function for the octree leaf count I implemented earlier to set the array to an appropriate size.

Answer 1

If you're going after code conciseness, I would use this:

int[] result = new int[8]; 
byte leafposition = 42;
int arrayPosition = 0;
for (int iteration = 0; iteration < 8; ++iteration)
    if ((leafposition & (1 << iteration)) != 0)
        result[arrayPosition++] = iteration + 1;   // one-indexed

If you're going after performance, I would use a pre-populated array (of 256 entries). You can either generate this statically (at compile-time) or lazily (before calling your method the first time).

int[][] leaves =
{
    /* 00000000 */ new int[] { },
    /* 00000001 */ new int[] { 1 },
    /* 00000010 */ new int[] { 2 },
    /* 00000011 */ new int[] { 1, 2 },
    /* 00000100 */ new int[] { 3 },
    /* 00000101 */ new int[] { 1, 3 },
    /* 00000110 */ new int[] { 2, 3 },
    /* 00000111 */ new int[] { 1, 2, 3 },
    /* 00001000 */ new int[] { 4 },
    /* 00001001 */ new int[] { 1, 4 },
    /* ... */
};

byte leafposition = 42;
int[] result = leaves[leafposition];

Edit: If you're using the lookup table and can afford a one-time initialization (that will be amortized through many subsequent uses), I would suggest creating it dynamically (rather than bloating your source code). Here's some sample code in LINQ; you can use the loop version instead.

int[][] leaves = new int[256][];
for (int i = 0; i < 256; ++i)
    leaves[i] = Enumerable.Range(0, 8)
                          .Where(b => (i & (1 << b)) != 0)
                          .Select(b => b + 1)
                          .ToArray();