CODEWITHSUNDEEP
c#arraysbinarybit-manipulation
John Smith
John Smith

Reputation: 8801

Fastest way to get consecutive index of each set bit?

Let's say I have an integer and its binary representation is thus:

1001 1011 0111 0001 0010 1100 1000 1111

I'm looking for a way to get the consecutive index of each set bit. I'm moving array elements from one array to another. The number of elements is the number of ones.

In this example, the first 4 elements of the first array would be moved to the first 4 indicies of the second array (start from the right side: the LSB).

However, after that, the fifth element of the first array would instead move to the 8th index of the second array because there is a gap of 3 zeroes (so 8th index = index 7).

Hopefully you can see the pattern by now. I thought of possibly converting to a string and doing a loop, but that seems rather slow. I could also use some bit-manipulation like this in a loop:

x & (x-1) to clear next set bit

and

(int)Math.Log((x & ~(x - 1)), 2); to find next set bit.

There's also the solution with just keeping a running index and keep anding by 1 and shifting by 1 each iteration.

But I'm not sure if there are better ways or if I'm missing something that is much simpler.

Upvotes: 0

Views: 1312

Answers (1)

Alex
Alex

Reputation: 13224

I would think that a simple loop with a running index should work fine. Calls to Math.Log will definitely not be faster, nor will De Bruijn bit hacking operations. If it were possible to do assembly/intrinsics to find leading/trailing 0s in c# possibly something better could be done.

For now, I would suggest the simple loop, with a termination criterion for when mask has become 0, as in:

static void CopyByMask<T>(UInt32 mask, T[] srcArray, T[] destArray)
{
    // Note: assumes arrays are appropriately sized.
    var srcPos = 0;
    for (var destPos = 0; mask != 0; destPos++)
    {
        if ((mask & 1) == 1)
            destArray[destPos] = srcArray[srcPos++];
        mask >>= 1;
    }
}

Upvotes: 3

Related Questions