从位内'std :: vector'

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,16,32或64位wside
• 整数被存储在大端排序的整数8个比特

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); 

你会得到其对应比特串00000000 00101010正确的结果是53290与位串11010000 00101010结果42。注意最右边的4位是如何被清零的。这是因为你首先通过改变你的value变量，使这四位移出变量。在最后移回时，这会导致位被清零。

第二个问题与最后的右移有关。如果value变量的最右边的位在最后的右移之前碰巧是1，并且模板参数是带符号的类型，则完成的右移是'算术'右移，这会导致被填满的权利，给你一个不正确的负值。

例如，尝试运行：

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

预期的结果应该是6976与位串00011011 01000000，但目前执行与位串11111011 01000000返回-1216。

我已经把我的执行本低于从建立到左右的比特串，将位正确位置下手，这样避免了上述两个问题：

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

Answer 2

有趣的问题。我做了类似的工作，因为有些系统工作。

• 你的char是8位宽？还是16？你的整数有多大？ 32或64？
• 忽略一分钟的向量复杂性。
• 认为它只是一个位数组。
• 你有多少位？你有8 *字符数
• 你需要计算一个起始字符，要提取的位数，结束字符，位数和中间字符数。
• 你需要按位与&的第一部分字符
• 则需要按位与&最后部分字符
• 则需要左移< <（或右移>>）取决于您从哪个订单开始
• Integer的排序是什么？

在某些时候你会计算索引你的数组，它是bitIndex处/ char_bit_width，你给值171作为bitIndex处和8作为您char_bit_width，所以你将最终计算出这些有用的值：

• 8分之171= 23 //第一个字节的位置
• 171％8 =在第一个字符/字节3个//比特
• 8 - 171％8 = 5在最后一个字符//比特/字节
• sizeof（integer）= 4
个
• 的sizeof（整数）+（（171％8）> 0？1：0）//多少排列位置，以检验

一些集会要求...

Answer 3

有一件事你肯定错过了我的想法：您向量中的位索引的方式与您在问题中给出的方式不同。即使用您列出的算法，这些位的顺序将如7 6 5 4 3 2 1 0 | 15 14 13 12 11 10 9 8 | 23 22 21 ...。坦率地说，我没有读通过你的整个算法，但是这一个在第一步中错过了。