Check specific bit of QByteArray

I have an 8 byte QByteArray and I need to check a specific bit in that array, but not the same bit every time. It could be any of the 64 bits that make up that 8 byte array. Performance is priority!

My current method first grabs a specific byte from that array, then gets a specific half-byte (or nibble), and then converts to another QByteArray with binary representation using QByteArray::number(x, 2), and then finally I check the bit. This sucks and I want a better way.

I opted to load it into a QBitArray so I can quickly and easily retrieve a specific bit. I assumed its representation in memory is the same as a QByteArray or quint64, so conversion would be accepted, but conversion is not allowed.

How would I check if a specific bit (0 to 63) in a QByteArray is 1 or 0, quickly?

Solution

QBitArray wasn't designed to be convertible to anything else; its internal representation is indeed internal.

Alas, bit checking is rather easy. Modern architectures use barrel shifters, so shifting is cheap.

There are several possible bit-to-byte mappings. Let's cover all of them:

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

Thus:

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

If we assume that the platform has sensible support for 64-bit integers, we can leverage those:

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

Any decent compiler will inline either implementation above when specialized, e.g.

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

You can also specialize it by hand for the LB case:

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

Note that the Q_BYTE_ORDER check is a compile-time constant and incurs no runtime overhead.

getBit1 and getBit2 are portable to all platforms Qt runs on, and getBit2 generates a little better code than getBit1. On x86-64, the bit twiddling code from getBit2 amounts to 5 instructions:

mov    $0x1,%eax
shl    %cl,%eax
cltq   
test   %rax,(%rdi)
setne  %al
retq