Is there a fast method to extract bits by index (not just masking)?

Question

I have a certain binary number for example: 11110000 And a mask with exactly 4 bits set: 10101010 Im searching for a fast operation that would return the 4 bits of the input corresponding to the positions where the mask is set:

11110000 10101010 output:1100

In here I use a u8 to u4 but imagine this for u64 to u32. Is there a fast way to do this (in Rust or C) without looping?

I tried looping the indexes, and linear decomposition. Both are very slow as one requires looping the other requires a matrix decomposition.

Answer 1

If you can preprocess your selection mask, then you can do this in log(width) number of mask-and-shift operations.

If your selection mask has any odd-sized gaps in it, then you can first apply a mask of bits to shift one position to the right, with the result that there will only be even-sized gaps between the bits you want.

Starting with a selection mask of 10101010, for example, the bits to shift to the right 1 place are 00100010. After shifting those bits, the new selection mask to apply is 10011001, which has only even-sized gaps.

Then there is a mask for shifting 2 positions to the right that will make all your gap sizes divisible by 4: 10011001 -> 10000111

If you continue this way until the gap size is divisible by the word size, then there won't be any gaps: 10000111 -> 00001111

To calculate these masks, first calculate the total shift required for each bit position. The first mask clears the 1 bit from all odd total shifts. The second mask clears the 2 bits, etc.