Bitwise Comparison Efficiency

Question

I have an array of type uint8_t. 0 in a bit means 'OK', 1 means 'ERROR'. Each bit represents a different system.

I have to call error function if any error is detected in a bit. My solution is the following:

const int arrSize = 3;
void bitComparator() {
uint8_t myArr[arrSize] = {0, 1, 64}; //array storing system status
uint8_t mask; //bit mask
uint8_t maskResult;
for(int i=0; i<arrSize; i++) {
  mask = 1; // mask is 0000 0001
  for(int j=0; j<8; j++) {
    maskResult = mask & myArr[i];
    if(maskResult != 0) errFunc(i, j);
    mask <<= 1;
  }
}

If myArr is as wide as n, then the solution is O(n) complexity. Could you suggest any improvement on the solution regarding complexity or efficiency? It might as well be already OK, but I am not sure.

Note: I need to know the position having error.

Does [this](https://stackoverflow.com/questions/9829578/fast-way-of-counting-non-zero-bits-in-positive-integer) answers your question? — Tim, Dec 06 '19 at 16:04
@Tim He needs to know the positions as well, not just the count. — imreal, Dec 06 '19 at 16:05
You could have a precomputed table. Maybe a `vector` of `vectors`. — imreal, Dec 06 '19 at 16:06
I am not sure you can reduce lower than O(n). But you can certainly parallelize, since you are only reading `myArr`. I would suggest to *vectorize* the inner loop and *parallelize* the outer one. — Tim, Dec 06 '19 at 16:10
What's the goal here? To call `errFunc` for each bit in the array that is not zero? — NathanOliver, Dec 06 '19 at 16:11
Something like `vector>` where the first vector is indexed by the value of the `uint8` and the second `vector` is a list of true bits, the value is the position. — imreal, Dec 06 '19 at 16:12
@NathanOliver-ReinstateMonica, definetely, `errorFunc` will mark the position and send a message to the target system. — Erdem Tuna, Dec 06 '19 at 16:13
you cannot do better than reading all bytes when you need to read all bytes. Not sure how you want to avoid `O(n)` — 463035818_is_not_an_ai, Dec 06 '19 at 16:14
Two comments. First, if `myArr[i]` is 0, you don't have to check its individual bits. Second, how many bits are you dealing with in the real problem, and how often do you have to check them? Unless it's a huge number of bits and a very high frequency of checking, I doubt that this code would be a bottleneck. — Pete Becker, Dec 06 '19 at 16:19
If you're expecting your data to pass as OK the majority of the time, maybe instead of comparing bit by bit every single time, try comparing your `myArr` with a mask of `00000000` before checking each bit. If it's identical to `00000000` there are no errors and individual bits won't need to be checked. This is still O(n) but will be a smaller O(n) than the one you currently have implemented. This will only be noticeably faster if you *mostly* don't have failing bits. Otherwise the branching may eliminate any speedups. — alteredinstance, Dec 06 '19 at 16:21
@formerlyknownas_463035818, I am not sure how it can be avoided, so wanted to consult the community. — Erdem Tuna, Dec 06 '19 at 16:25
@PeteBecker, the array is indeed it is 64 bits and question popped in my mind what if it were 128 or 256 or higher. Thank you for the suggestion. — Erdem Tuna, Dec 06 '19 at 16:25
@ErdemTuna then I would say see if you can use an `unsigned long long` (if your codes are 64 bits) to compare against `0` before doing any bit-checking. Your maximum comparisons will go up by 1, but your average number of comparisons will drop to nearly 1. Right now your code is O(8n), this shortcut may put you close to amortized O(n). If you go above 64 bits though, I don't really have a solution for that. You might be able to use multiple `ulonglong`'s, lol — alteredinstance, Dec 06 '19 at 16:34

score 1 · Answer 1 · answered Dec 06 '19 at 16:19

Since you need to call errFunc for each set bit then you need an O(N) solution since you have to visit every bit. You can make life a little easier and use a std::bitset which would make the code look like

void errFunc(int index, int bit)
{
    std::cout << "Error in index " << index << " bit " << bit << "\n";
}

const int arrSize = 3;
void bitComparator() 
{
    uint8_t myArr[arrSize] = {0, 1, 64}; //array storing system status
    for(int i=0; i<arrSize; i++) 
    {
        std::bitset<8> bitset{myArr[i]};
        for(int j=0; j<8; j++) 
        {
            if(bitset[j]) 
                errFunc(i, j);
        }
    }
}

int main()
{
    bitComparator();
}

which has the output of

Error in index 1 bit 0
Error in index 2 bit 6

Pete Becker · Answer 2 · 2019-12-06T16:37:16.950

1

How common are errors? That is, will there be a bunch of bits set most of the time? If not, divide and conquer:

if (myArr[i] != 0)
    if(myArr[i] & 0x0F)
        // process low 4 bits
    if (myArr[i] & 0xF0)
        // process high 4 bits

edited Dec 06 '19 at 16:37

answered Dec 06 '19 at 16:25

Pete Becker

74,985
8
76
165

does `process` mean masking the bits as in the original code? – Erdem Tuna Dec 06 '19 at 16:28
@ErdemTuna -- it means "process". It could be by masking Individual bits, or it could be by divide and conquer again. Since you mentioned that your actual problem deals with 64 bits, I'd use a 64-bit unsigned integer type to hold the bits (rather than an array of 8-bit integers). Checking for no errors is simple, and if there are errors you can split it a couple of times before reverting to masking individual bigs. – Pete Becker Dec 06 '19 at 16:32
What if there are errors in both the low and high bits? I see what you're getting at but this will lead to unexpected behavior if, for example, an error code of `01000110` is encountered – alteredinstance Dec 06 '19 at 16:36
@alteredinstance -- whoops, typo in the code. Fixed. Thanks. – Pete Becker Dec 06 '19 at 16:37
No worries - the only thing I'd wonder now is the expensiveness of branching so many times in what *could* be linear code. This could be quite a time saver with the 64 bit error codes @ErdemTuna said was going to be used. For smaller error codes (8/16 bit), however, divide and conquer with if-statements could do more harm than good at runtime! – alteredinstance Dec 06 '19 at 16:43

Bitwise Comparison Efficiency

2 Answers2