从`std :: vector <char>`里面的位获取整数

Question

我有一个vector<char>,我希望能够从向量中的一系列位获得无符号整数.例如

我似乎无法编写正确的操作来获得所需的输出.我想要的算法是这样的:

• & 第一个字节用 (0xff >> unused bits in byte on the left)
• << 结果留下了输出字节数*一个字节的位数
• | 这与最终输出
• 对于每个后续字节:
  • << 由每个字节的(字节宽度 - 索引)*位左边
  • | 这个字节带有最终输出
• | 最终输出的最后一个字节(未移位)
• >> 最终输出由右边字节中未使用的位数

这是我尝试编码它,但没有给出正确的结果:

#include <vector>
#include <iostream>
#include <cstdint>
#include <bitset>

template<class byte_type = char>
class BitValues {
    private:
    std::vector<byte_type> bytes;
    public:
        static const auto bits_per_byte = 8;
        BitValues(std::vector<byte_type> bytes) : bytes(bytes) {
        }
        template<class return_type>
        return_type get_bits(int start, int end) {
            auto byte_start = (start - (start % bits_per_byte)) / bits_per_byte;
            auto byte_end = (end - (end % bits_per_byte)) / bits_per_byte;
            auto byte_width = byte_end - byte_start;
            return_type value = 0;

            unsigned char first = bytes[byte_start];
            first &= (0xff >> start % 8);
            return_type first_wide = first;
            first_wide <<= byte_width;
            value |= first_wide;

            for(auto byte_i = byte_start + 1; byte_i <= byte_end; byte_i++) {
                auto byte_offset = (byte_width - byte_i) * bits_per_byte;
                unsigned char next_thin = bytes[byte_i];
                return_type next_byte = next_thin;
                next_byte <<= byte_offset;
                value |= next_byte;
            }
            value >>= (((byte_end + 1) * bits_per_byte) - end) % bits_per_byte;

            return value;
        }
};

int main() {
    BitValues<char> bits(std::vector<char>({'\x78', '\xDA', '\x05', '\x5F', '\x8A', '\xF1', '\x0F', '\xA0'}));
    std::cout << bits.get_bits<unsigned>(15, 29) << "\n";
    return 0;
}

(在行动中:http://coliru.stacked-crooked.com/a/261d32875fcf2dc0)

我似乎无法绕过这些位操作,我发现调试非常困难!如果有人能够纠正上述代码,或以任何方式帮助我,我将不胜感激!

编辑:

• 我的字节长8位
• 要返回的整数可以是8,16,32或64位
• 整数存储在big endian中

Answer 1

你犯了两个主要错误。第一个在这里：

first_wide <<= byte_width;

您应该移动位数，而不是字节数。更正后的代码是：

first_wide <<= byte_width * bits_per_byte;

第二个错误在这里：

auto byte_offset = (byte_width - byte_i) * bits_per_byte;

它应该是

auto byte_offset = (byte_end - byte_i) * bits_per_byte;

括号中的值需要是要右移的字节数，也是 byte_i 距离末尾的字节数。该值byte_width - byte_i没有语义意义（一个是增量，另一个是索引）

其余的代码都很好。不过，该算法有两个问题。

首先，当使用结果类型来累加位时，您假设左侧有空闲空间。如果在右边界附近有设置位并且范围的选择导致这些位被移出，则情况并非如此。例如，尝试运行

bits.get_bits<uint16_t>(11, 27);

您将得到与位串对应的结果 42。00000000 00101010正确的结果是位串 53290 11010000 00101010。请注意最右边的 4 位是如何被清零的。这是因为您一开始就对value变量进行了过度移位，导致这四位从变量中移出。当最后移回时，这会导致位被清零。

第二个问题与最后的右移有关。如果变量的最右边的位value在末尾右移之前恰好是 1，并且模板参数是有符号类型，则所做的右移是“算术”右移，这会导致右侧的位被 1 填充，留下一个不正确的负值。

例如，尝试运行：

bits.get_bits<int16_t>(5, 21);

预期结果应该是 6976（带有位字符串）00011011 01000000，但当前实现返回-1216（带有位字符串）11111011 01000000。

我将我的实现放在下面，它从右到左构建位字符串，将位放置在正确的位置开始，以便避免上述两个问题：

template<class ReturnType>
ReturnType get_bits(int start, int end) {
  int max_bits = kBitsPerByte * sizeof(ReturnType);
  if (end - start > max_bits) {
    start = end - max_bits;
  }

  int inclusive_end = end - 1;
  int byte_start = start / kBitsPerByte;
  int byte_end = inclusive_end / kBitsPerByte;

  // Put in the partial-byte on the right
  uint8_t first = bytes_[byte_end];
  int bit_offset = (inclusive_end % kBitsPerByte);
  first >>= 7 - bit_offset;
  bit_offset += 1;
  ReturnType ret = 0 | first;

  // Add the rest of the bytes
  for (int i = byte_end - 1; i >= byte_start; i--) {
    ReturnType tmp = (uint8_t) bytes_[i];
    tmp <<= bit_offset;
    ret |= tmp;
    bit_offset += kBitsPerByte;
  }

  // Mask out the partial byte on the left
  int shift_amt = (end - start);
  if (shift_amt < max_bits) {
    ReturnType mask = (1 << shift_amt) - 1;
    ret &= mask;
  }
}