高效过滤比特串

Question

高效过滤比特串

5

我正在寻找一个位操作函数，它可以接受两个位字符串作为输入，并根据第二个字符串对第一个字符串进行过滤和压缩，只保留第二个字符串中值为1的位。例如：

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

通过使用循环、条件语句和独立处理每个位，这很容易实现，但如果存在一种更快的比特操作技巧的话，我正在寻找这种方法，而不是使用条件语句和循环。它不必处理超过 32 位的输入。因此，解决方案的签名将如下：uint32_t filter(uint32_t in, uint32_t mask)

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

以下是我正在寻找的各种解决方案的一些示例：位操作技巧

- Björn Ottosson

3

你确定01101010和11110000的结果是00000110吗？你是通过什么推断出来的？ - alinsoar

从右侧索引，前四位将被跳过，接下来的四位将被保留，因此0110将被保留并向右移动。 - Björn Ottosson

如果您从右到左索引输出，则应将 output_index 减少而不是增加。 - alinsoar

1

这取决于您如何索引位串，假设最低有效位先索引，因此位串的索引为76543210，请参阅squeamish ossifrage的答案以了解如何处理。 - Björn Ottosson

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- r3mainer · 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 %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;
}