Bit string filtering efficiently

Question

I am looking for a small manipulation function that takes two bit strings and filters and compacts the first string based on the second, so only the values ​​are saved where the second string is 1. For example:

01101010 and 11110000 gives 00000110 01101010 and 00001111 gives 00001010 01101010 and 10101000 gives 00000011 

Using a loop, conditional expressions, and working with each bit independently, this is easy to implement, but I'm looking for a faster method using techniques for manipulating bits if it exists, rather than using conditional expressions and loops . It should not work for input over 32 bits. Therefore, the solution should have such a signature as: uint32_t filter (uint32_t in, uint32_t mask)

In C, it will look something like this: arrays and a loop:

 void filter(bool in[], bool mask[], bool out[], int size) { int output_index = 0; for (int input_index = 0; input_index < size; ++input_index) { if (mask[input_index]) { out[output_index++] = in[input_index]; } } } 

Here are some examples of the types of solutions I'm looking for: Twiddling Hacks Bit

Answer 1

If you need to store bit sequences up to 32 bits, it would be much more efficient to store them as unsigned 32-bit integers. Here is one way to do this:

 #include <stdio.h> #include <stdint.h> uint32_t filter(uint32_t in, uint32_t mask) { uint32_t result=0, t, p=1, q=1; while (mask) { if ( (t = mask & 1) ) { if ( (q & in) ) result |= p; p <<= 1; } mask >>= 1; q <<= 1; } return result; } int main() { /* 01101010 and 11110000 gives 00000110 */ printf("%04x %04x %04x\n", 0x6a, 0xf0, filter(0x6a,0xf0)); /* Output: 0006 */ /* 01101010 and 00001111 gives 00001010 */ printf("%04x %04x %04x\n", 0x6a, 0x0f, filter(0x6a,0x0f)); /* Output: 000a */ /* 01101010 and 10101000 gives 00000011 */ printf("%04x %04x %04x\n", 0x6a, 0xa8, filter(0x6a,0xa8)); /* Output: 0003 */ return 0; }