C语言 有效过滤位串

Question

>我正在寻找一个位操作函数，它接受两个位字符串并根据第二个字符串过滤并压缩第一个字符串，因此只保留第二个字符串为 1 的值。例如：

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

通过使用循环、条件和独立处理每个位，这很容易实现，但我正在寻找一种使用位操作技巧(如果存在(的更快方法，而不是使用条件和循环。它不必适用于长度超过 32 位的输入。因此，解决方案将具有如下签名： uint32_t过滤器(uint32_t in，uint32_t掩码(

在 C 中，数组和循环看起来像这样：

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];
}
}
}

以下是我正在寻找的解决方案类型的一堆示例： 有点叽叽喳喳的黑客

Answer 1

如果您只需要存储最多 32 位的位序列，则将它们存储为 32 位无符号整数会更有效。这是一种方法：

#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 %04xn", 0x6a, 0xf0, filter(0x6a,0xf0)); /* Output: 0006 */
/* 01101010 and 00001111 gives 00001010 */
printf("%04x %04x %04xn", 0x6a, 0x0f, filter(0x6a,0x0f)); /* Output: 000a */
/* 01101010 and 10101000 gives 00000011 */
printf("%04x %04x %04xn", 0x6a, 0xa8, filter(0x6a,0xa8)); /* Output: 0003 */
return 0;
}