检查 QByteArray 的特定位

Check specific bit of QByteArray

我有一个 8 字节 QByteArray,我需要检查该数组中的特定位,但每次都不是相同的位。它可以是构成该 8 字节数组的 64 位中的任何一位。性能优先!

我当前的方法首先从该数组中获取一个特定的字节,然后获取一个特定的半字节(或半字节),然后使用 QByteArray::number(x, 2) 转换为另一个 QByteArray 二进制表示,并且最后我检查了一下。这很糟糕,我想要一个更好的方法。

我选择将它加载到 QBitArray 中,这样我就可以快速轻松地检索特定位。我假设它在内存中的表示与 QByteArrayquint64 相同,因此可以接受转换,但不允许转换。

如何快速检查 QByteArray 中的特定位(0 到 63)是 1 还是 0?

QBitArray 并非设计为可转换为其他任何东西;它的内部表示确实是内部的。

唉,位检查是相当容易的。现代建筑使用桶形移位器,所以移位很便宜。

有几种可能的位到字节映射。让我们涵盖所有这些:

        byte 0     byte 1       byte n-1   byte n
LL - [01234567] [89ABCDEF] ...
LB - [76543210] [FEDCBA98] ...
BL -                       ... [89ABCDEF] [01234567]
BB -                       ... [FEDCBA98] [76543210]

因此:

enum class BitMapping { LL, LB, BL, BB };

bool getBit1(const QByteArray & arr, int bit, BitMapping m) {
  Q_ASSERT(arr.size() >= 8);
  auto byte = (m == BitMapping::LL || m == BitMapping::LB) ? 
              bit/8 : (7 - bit/8);
  bit = (m == BitMapping::LB || m == BitMapping::BB) ?
        (bit%8) : (7 - (bit%8));
  return arr.at(byte) & (1<<bit);
}

如果我们假设平台对 64 位整数有合理的支持,我们可以利用这些:

bool getBit2(const QByteArray & arr, int bit, BitMapping m) {
   Q_ASSERT(arr.size() >= 8);
   auto value = *reinterpret_cast<const quint64 *>(arr.data());
   if (m == BitMapping::LL || m == BitMapping::BL)
      bit = (bit & 0x38) + 7 - (bit & 0x07); // reorder bits
   if ((Q_BYTE_ORDER == Q_LITTLE_ENDIAN && (m == BitMapping::BL || m == BitMapping::BB)) ||
       (Q_BYTE_ORDER == Q_BIG_ENDIAN && (m == BitMapping::LL || m == BitMapping::LB)))
      bit = (bit & 0x07) + 0x38 - (bit & 0x38); // reorder bytes
   return value & (1<<bit);
}

任何体面的编译器都会在专门化时内联上述任一实现,例如

bool getBit(const QByteArray & arr, int bit) {
  return getBit2(arr, bit, BitMapping::LB);
}

您也可以针对 LB 情况手动对其进行专门化:

bool getBit1(const QByteArray & arr, int bit) {
  Q_ASSERT(arr.size() >= 8);
  auto byte = bit/8;
  bit = bit%8;
  return arr.at(byte) & (1<<bit);
}

bool getBit2(const QByteArray & arr, int bit) {
   Q_ASSERT(arr.size() >= 8);
   auto value = *reinterpret_cast<const quint64 *>(arr.data());
   if (Q_BYTE_ORDER == Q_BIG_ENDIAN)
      bit = (bit & 0x07) + 0x38 - (bit & 0x38); // reorder bytes
   return value & (1<<bit);
}

请注意,Q_BYTE_ORDER 检查是编译时常量,不会产生运行时开销。

getBit1getBit2 可移植到 Qt 运行的所有平台,并且 getBit2 生成的代码比 getBit1 好一点。在 x86-64 上,来自 getBit2 的位旋转代码总计 5 条指令:

mov    [=15=]x1,%eax
shl    %cl,%eax
cltq   
test   %rax,(%rdi)
setne  %al
retq   

我猜你需要做的就是遍历位。

1) 检查你想要的位

if(j+(i*CHAR_BIT) == (bit-1)) 

2) 如果传递的 'bit' 不适合特定字节

,则跳过不需要的字节
(((i+1)*CHAR_BIT) < (bit-1))

3) 如果当前位位置大于传递的位,则跳过所有后续字节。

((j+(i*CHAR_BIT)) > (bit-1))

下面是完整的解决方案。

quint8 checkBit(QByteArray bytes, int bit) {
    quint8 result=0;
    for(int i = 0; i < bytes.count(); ++i) {
        for (int j = 0; j < CHAR_BIT; ++j) {
            if(j+(i*CHAR_BIT) == (bit-1)) {
                result = (bytes.at(i) & (1 << (7-j))) ? 1 : 0;
                break;
            }
            else if(((i+1)*CHAR_BIT) < (bit-1) || ((j+(i*CHAR_BIT)) > (bit-1))) { // out of range skips
                break;
            }
        }
    }

    return result;
}

注意:因为位置是从0开始的,所以当你传bit的时候..说8其实就是8-1 = 7 : [0,1,2,3,4,5,6,7]