读取 n 位并用零填充的通用算法

Question

我需要一个函数来读取从位x开始的n位（位索引应该从零开始），如果结果不是字节对齐的，用零填充它。该函数将在输入上接收 uint8_t 数组，并且还应接收 return uint8_t 数组。例如，我有以下内容的文件：

1011 0011 0110 0000

从第三位开始读取三位(x=2,n=3);结果：

1100 0000

输入和位模式长度没有（理论上的）限制

Answer 1

在不超出直接位串行算法的情况下有效地实现这样的位域提取并不完全困难，但有点麻烦。

实际上它可以归结为一个内部循环，从输入中为每个输出字节读取一对字节，根据源位偏移将结果字移位到位，然后写回高位或低位字节。此外，最终输出字节根据长度进行屏蔽。

以下是我的（未经过充分测试的）实现尝试：

void extract_bitfield(unsigned char *dstptr, const unsigned char *srcptr, size_t bitpos, size_t bitlen) {
    // Skip to the source byte covering the first bit of the range
    srcptr += bitpos / CHAR_BIT;
    // Similarly work out the expected, inclusive, final output byte
    unsigned char *endptr = &dstptr[bitlen / CHAR_BIT];
    // Truncate the bit-positions to offsets within a byte
    bitpos %= CHAR_BIT;
    bitlen %= CHAR_BIT;
    // Scan through and write out a correctly shifted version of every destination byte
    // via an intermediate shifter register
    unsigned long accum = *srcptr++;
    while(dstptr <= endptr) {
        accum = accum << CHAR_BIT | *srcptr++;
        *dstptr++ = accum << bitpos >> CHAR_BIT;
    }
    // Mask out the unwanted LSB bits not covered by the length
    *endptr &= ~(UCHAR_MAX >> bitlen);
}

请注意，上面的代码可能会读取到源缓冲区的末尾，如果您不能设置开销来允许这样做，则需要进行一些混乱的特殊处理。它还假设 sizeof(long) != 1.

当然，为了提高效率，您需要尽可能广泛地使用本地词。但是，如果目标缓冲区必须字对齐，那么事情会变得更加混乱。此外，little-endian 系统将需要字节混合修复。

另一个需要注意的微妙之处是可能无法移位整个单词，即移位计数经常以单词长度为模来解释。

无论如何，快乐的 bit-hacking！

Answer 2

基本上还是一堆移位和加法运算

我将使用一个稍微大一点的例子来证明这一点。

假设我们要输入 4 个字符，并且 x = 10，n = 18。

00101011 10001001 10101110 01011100

首先，我们需要通过 x / 8 定位包含我们第一位的字符，在本例中为我们提供 1（第二个字符）。我们还需要该字符的偏移量 x % 8，等于 2。

现在三个运算就可以得到解的第一个字符

将第二个字符 10001001 左移 2 位，得到 00100100。
将第三个字符 10101110 右移 6（来自 8 - 2）位，得到 00000010。
添加这两个字符给我们您的 return 字符串中的第一个字符，给出 00100110。

将此例程循环 n / 8 轮。如果 n % 8 不为 0，则从下一个字符中提取那么多位，您可以通过多种方法实现。

所以在这个例子中，我们的第二轮会给我们10111001，最后一步我们得到10，然后用0填充其余位。

读取 n 位并用零填充的通用算法

General algorithm for reading n bits and padding with zeros

c++

file

bitmap

bit-manipulation