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.

It is not really that slow to reallocate an array. Whether it is too slow for your purposes is a different matter (since this is presumably inner loop code called often). You might consider calculating the Hamming weight first (number of bits set to 1) so that you can allocate an array of appropriate size, and measure the two approaches. http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer — Eric J., May 19 '13 at 17:35
You know, this is why I'm asking here. The last method I was writing was just about getting the leaf count as fast as possible... Can't believe I'm not thinking about my own code when doing this. Thank you so much for the most obvious idea! — HaMster, May 19 '13 at 19:48

Douglas · Accepted Answer · 2013-05-19T20:15:11.833

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();

Since this is just a byte, a lookup table is probably the fastest way to do this. Thank you for the idea! — HaMster, May 19 '13 at 19:50
@EricJ. except for the performance lost constructing the lookup table. — Jodrell, Jun 16 '15 at 09:55
@Jodrell: The lookup table is O(1) if you compile it in, which you can do if the O(N) time to construct the lookup table at runtime makes a difference. — Eric J., Jun 16 '15 at 17:15
what about 64bit (ulong), I suppose the pre-populated array solution doesn't fit due to it's huge size of combinations, is that right? would the bits iteration the only way to go? or is there a faster way? — Oswaldo, May 31 '22 at 00:03

score 0 · Answer 2 · answered May 30 '15 at 06:47

Here's a C-style solution that uses __builtin_ffs

int arrayPosition = 0;
unsigned int tmp_bitmap = original_bitfield;        
while (tmp_bitmap > 0) {
    int leafposition = __builtin_ffs(tmp_bitmap) - 1;
    tmp_bitmap &= (tmp_bitmap-1);
    result[arrayPosition++] = leafposition;
}

Jodrell · Answer 3 · 2015-06-16T09:58:01.213

how about,

public static IEnumerable<int> LeafPositions(byte octet)
{
    for (var i = 1; octet > 0; octet >>= 1, i++)
    {
        if ((octet & 1) == 1)
        {
            yield return i;
        }
    }
}

or, easier to read in my opinion.

IEnumerable<int> LeafPositions(byte octet)
{
    if ((octet & 1) == 1) yield return 1;
    if ((octet & 2) == 2) yield return 2;
    if ((octet & 4) == 4) yield return 3;
    if ((octet & 8) == 8) yield return 4;
    if ((octet & 16) == 16) yield return 5;
    if ((octet & 32) == 32) yield return 6;
    if ((octet & 64) == 64) yield return 7;
    if ((octet & 128) == 128) yield return 8;
}

Or, going to extremes

IEnumerable<int> LeafPositions(byte octet)
{
    switch (octet)
    {
        case 1:
            yield return 1;
            break;

        case 2:
            yield return 2;
            break;

        case 3:
            yield return 1;
            yield return 2;
            break;

        ...

        case 255:
            yield return 1;
            yield return 2;
            yield return 3;
            yield return 4;
            yield return 5;
            yield return 6;
            yield return 7;
            yield return 8;
            break;
    }

    yield break;
}

find set bits positions in a byte

3 Answers3