Problems with Open-Source Downloads read https://www.qt.io/blog/problem-with-open-source-downloads and https://forum.qt.io/post/638946

[Solved] Quickly test QBitArray bytes to see if all are zero



  • I have a QBitArray that has a bunch of bit flags. I wonder if there is a fast way to test if all the bytes used internally in the QBitArray are zero. I can go through them one bit a time. But seems like it could be done faster if I could get at the bytes.

    Thanks



  • What about:
    @
    if (bitArray.count(true) == 0) { }
    @
    The way that is implemented should be much faster than a brute force iteration.

    Or even this:
    @
    if (bitArray == QBitArray(bitArray.size(), false)) { }
    @
    If the bit array size is fixed then you could make the RHS a const outside the if().



  • The fasted method probably would be to run a memcmp() on the constData() of the QBitArray's internal QByteArray. But that isn't exposed to the public. So you are stuck with count() which already does quite some bit magic...

    http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel



  • The count() function does what I needed. But still this is a not perfectly suited for what I want.

    My particular need I just wanted a super fast way to see if any bits were set. I don't need to have a count, but this will work fine.

    If anyone from Qt is listening, it would be nice if the QBitArray had a fast test to see if any bits were set.



  • If you exclusively modify the Bit vector through QBitArray.setBit(), you could overwrite that method and update a flag of your own. You'd only need to maintain a counter of the "1" bits that is updated at each call. Then you could check for "all bits are zero" in constant time by reading the counter.

    @void MyBitArray::setBit(int i, bool value)
    {
    if(testBit(i) != value)
    {
    if(value) m_oneCounter++; else m_oneCounter--;
    QBitArray::setBit(i, value)
    }
    }

    bool MyBitArray::isAllZeros(void)
    {
    return (m_oneCounter == 0);
    }@



  • Actually, my second option, using operator==(), will not work. It only tests that the internal pointers are the same and does not check that bits themselves.


Log in to reply