我有一个 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方式存储
最佳答案
您犯了两个主要错误。第一个在这里:
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;
}
}
关于c++ - 从 `std::vector<char>` 内部的位获取整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19169753/