Efficient bitmask enumeration in C

Question

Say I have some bitmask, such as int b=0b1010110. Having another int m, there are 2^4=16 options on what m & b can be: the values of bits 1,2,4,6 of m & b can be all either 0 or 1 while all other values are 0.

I want to extract an integer between 0 and 15 from m & b as efficiently as possible, thereby discarding all the 0-bits in b.

It is easy to do in O(B) time (where b has B bits set) by just checking the specific bits of m. I want this to work independently of b, so no hard-coding of the bits of b. The bits of b are also available in an array.

Is there a bit-operation to do this faster, in O(1) or O(log B) or so?

Technically, since there is an upper bound on the bits to look at (32, 64, 128), your O(B) operations are actually O(1). Also, bitwise operations with no branching are *fast*. — tucuxi, Apr 27 '23 at 14:58
Related: https://stackoverflow.com/questions/25750844/how-can-i-shuffle-bits-efficiently — nwellnhof, Apr 27 '23 at 14:59
I guess I misunderstood the problem at first when suggested LUT. Still possible though, but not as trivial or beneficial over the "naive" approach.. — Eugene Sh., Apr 27 '23 at 15:10
If I understand it correctly, your `m & b` is misleading. You want to only take the bits of `m` which correspond to `1`'s in `b` and "concatenate" them into a 4-bit number. The `&` operation here is pretty much irrelevant. — Eugene Sh., Apr 27 '23 at 15:20
I suggest to add some naive source code to the question to show what exactly you want. Did you check that the code generated by a compiler with optimization enabled is not efficient? Is there a guarantee that `b` contains exactly 4 1-bits? What do you want to do with the result? Do you really need it to be in range 0..15? — Bodo, Apr 27 '23 at 15:20
I think you may be looking for the pext instruction. https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set — Simon Goater, Apr 27 '23 at 15:21
On Intel there may be specialized instructions for this: probably [pext](https://www.felixcloutier.com/x86/pext) as mentioned above? [Some bonus insanity.](https://stackoverflow.com/questions/36932240/avx2-what-is-the-most-efficient-way-to-pack-left-based-on-a-mask) — teapot418, Apr 27 '23 at 15:23
*The bits of b are also available in an array.* - can it be an array of set bit indices instead? Someone made this arrays somehow, so why not make it differently? — Eugene Sh., Apr 27 '23 at 15:27
@return true, Curious, why work with `int` and not `unsigned` for bit manipulation code? — chux - Reinstate Monica, Apr 27 '23 at 15:31

Efficient bitmask enumeration in C

0 Answers0