c# - find set bits positions in a byte -

i tyring create sparse octree implementation people @ nvidia ("efficient sparse voxel octrees") doing voxel things when came across issue:

i have bitfield of type byte (so 8 bits only) tells me leafs of octree (1 says leaf, 0 means no leaf, 8 nodes attached --> 8 bit). want returning array of leaf positions. current implementation using while loop find out if lsb set. input shifted 1 afterwards. here's how that:

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

this not looking elegant , has 2 things disturbing:

• this while loop mimics loop
• the result array smaller 8 values, resizing costly

i expect result [2,4,6] 42 (0010 1010).

can provide more elegant solution still readable?

---

result

i using function octree leaf count implemented earlier set array appropriate size.

if you're going after code conciseness, use this:

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

if you're going after performance, use pre-populated array (of 256 entries). can either generate statically (at compile-time) or lazily (before calling method 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 lookup table , can afford one-time initialization (that amortized through many subsequent uses), suggest creating dynamically (rather bloating source code). here's sample code in linq; can use loop version instead.

int[][] leaves = new int[256][]; (int = 0; < 256; ++i)     leaves[i] = enumerable.range(0, 8)                           .where(b => (i & (1 << b)) != 0)                           .select(b => b + 1)                           .toarray();