c++ - 从 `std::vector` 内部的位获取整数

Question

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

而且我似乎无法编写正确的操作来获得所需的输出。我的预期算法是这样的:

• &第一个字节 (0xff >> unused bits in byte on the left)
• <<结果剩下输出字节数 * 一个字节中的位数
• |这与最终输出
• 对于每个后续字节:
  • <<由 (byte width - index) * bits per byte 左边
  • |这个字节与最终输出
• |最终输出的最后一个字节(未移位)
• >>最终输出由右侧字节中未使用的位数

这是我尝试编写的代码，但没有给出正确的结果:

#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没有语义意义(一个是delta，另一个是index)

其余代码没问题。不过，该算法有两个问题。

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

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

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

第二个问题与最后的右移有关。如果 value 变量的最右边位恰好在末尾右移之前为 1，并且模板参数是有符号类型，则完成的右移是“算术”右移shift，这会导致右边的位被 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;
  }
}