5

我有一个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 位宽
  • 整数存储在大端
4

3 回答 3

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

您将得到对应于位串的结果 4200000000 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;
  }
}
于 2013-10-04T04:22:07.663 回答
0

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

于 2013-10-03T22:01:20.220 回答
0

有趣的问题。对于某些系统工作,我做过类似的事情。

  • 你的 char 是 8 位宽?还是16?你的整数有多大?32 还是 64?
  • 暂时忽略向量复杂度。
  • 把它想象成一个比特数组。
  • 你有多少位?你有 8*number of chars
  • 您需要计算起始字符、要提取的位数、结束字符、那里的位数以及中间的字符数。
  • 对于第一个部分字符,您将需要按位和 &
  • 对于最后一个部分字符,您将需要按位和 &
  • 您将需要左移 <<(或右移 >>),具体取决于您从哪个顺序开始
  • 你的整数的字节序是什么?

在某些时候,您将计算数组中的索引,即 bitindex/char_bit_width,您将值 171 作为您的 bitindex,并将 8 作为您的 char_bit_width,因此您最终将计算出这些有用的值:

  • 171/8 = 23 //第一个字节的位置
  • 171%8 = 3 //第一个字符/字节中的位
  • 8 - 171%8 = 5 //最后一个字符/字节中的位
  • 大小(整数)= 4
  • sizeof(integer) + ( (171%8)>0?1:0 ) // 要检查多少个数组位置

需要一些组装...

于 2013-10-03T21:56:21.997 回答