int count_pattern_occurrences( ... , uint8_t pattern = 0b101) {

That pattern default is nice, but solving a more general problem can make it difficult to optimize a quite specific one.

not the most efficient solution

I'm going to assume that means "not the fastest" solution.

One can finagle "O(1) space complexity" quite a bit. Lookup tables may be relevant here.

Consider that loop. Six of the first eight iterations examine strictly bits within a byte. Allocate a 256-byte lookup table of zeros, and assign a positive count to entries where the 0b101 pattern is embedded, e.g. entries 5 and 13 are part of that set. This solves part of the problem.

When scanning data in array,

• add lookup value to counter
• if data value ends with 10 then increment if next byte's LSB is set
• if data value MSB is set then increment if next byte's first two bits are 01

Notice that we can add a small value (1 or 2) to the counter and increment based on the next byte's masked value.

branch mispredictions

            if ((value ...) == pattern) {
                ++count;
            }

We have a data-dependent branch decision to make here, which essentially looks random to the predictor. Best it can do is predict that we usually skip the increment.

Use https://godbolt.org to learn whether your compiler was smart enough to rewrite this. If not, phrase it as count += (value ...) == pattern. That is, unconditionally add a boolean expression, to avoid mispredictions.

table based approach

int count_pattern_occurrences( ... , uint8_t pattern = 0b101) {

That pattern default is nice, but solving a more general problem can make it difficult to optimize a quite specific one.

not the most efficient solution

I'm going to assume that means "not the fastest" solution.

One can finagle "O(1) space complexity" quite a bit. Lookup tables may be relevant here.

Consider that loop. Six of the first eight iterations examine strictly bits within a byte. Allocate a 256-byte lookup table of zeros, and assign a positive count to entries where the 0b101 pattern is embedded, e.g. entries 5 and 13 are part of that set. This solves part of the problem.

When scanning data in array,

• add lookup value to counter
• if data value ends with 10 then increment if next byte's LSB is set
• if data value MSB is set then increment if next byte's first two bits are 01

Notice that we can add a small value (as much as 3) to the counter and increment based on the next byte's masked value.

int count_pattern_occurrences( ... , uint8_t pattern = 0b101) {

That pattern default is nice, but solving a more general problem can make it difficult to optimize a quite specific one.

not the most efficient solution

I'm going to assume that means "not the fastest" solution.

One can finagle "O(1) space complexity" quite a bit. Lookup tables may be relevant here.

Consider that loop. Six of the first eight iterations examine strictly bits within a byte. Allocate a 256-byte array of zeros, and assign a positive count to entries where the 0b101 pattern is embedded, e.g. entries 5 and 13 are part of that set. This solves part of the problem.

When scanning array,

• add lookup value to counter
• if array value ends with 10 then increment if next byte's LSB is set
• if array value MSB is set then increment if next byte's first two bits are 01

Notice that we can add a small value (1 or 2) to the counter and increment based on the next byte's masked value.

int count_pattern_occurrences( ... , uint8_t pattern = 0b101) {

That pattern default is nice, but solving a more general problem can make it difficult to optimize a quite specific one.

not the most efficient solution

I'm going to assume that means "not the fastest" solution.

One can finagle "O(1) space complexity" quite a bit. Lookup tables may be relevant here.

Consider that loop. Six of the first eight iterations examine strictly bits within a byte. Allocate a 256-byte lookup table of zeros, and assign a positive count to entries where the 0b101 pattern is embedded, e.g. entries 5 and 13 are part of that set. This solves part of the problem.

When scanning data in array,

• add lookup value to counter
• if data value ends with 10 then increment if next byte's LSB is set
• if data value MSB is set then increment if next byte's first two bits are 01

Notice that we can add a small value (1 or 2) to the counter and increment based on the next byte's masked value.

not the most efficient solution

I'm going to assume that means "not the fastest" solution.

One can finagle "O(1) space complexity" quite a bit. Lookup tables may be relevant here.

Consider that loop. Five of the first eight iterations examine strictly bits within a byte. Allocate a 256-byte array of zeros, and assign a positive count to entries where the 0b101 pattern is embedded, e.g. entries 5 and 13 are part of that set. This solves part of the problem.

When scanning array,

• add lookup value to counter
• if array value ends with 10 then increment if next byte's LSB is set
• if array value MSB is set then increment if next byte's first two bits are 01

Notice that we can add a small value (1 or 2) to the counter and increment based on the next byte's masked value.

int count_pattern_occurrences( ... , uint8_t pattern = 0b101) {

That pattern default is nice, but solving a more general problem can make it difficult to optimize a quite specific one.

not the most efficient solution

I'm going to assume that means "not the fastest" solution.

One can finagle "O(1) space complexity" quite a bit. Lookup tables may be relevant here.

Consider that loop. Six of the first eight iterations examine strictly bits within a byte. Allocate a 256-byte array of zeros, and assign a positive count to entries where the 0b101 pattern is embedded, e.g. entries 5 and 13 are part of that set. This solves part of the problem.

When scanning array,

• add lookup value to counter
• if array value ends with 10 then increment if next byte's LSB is set
• if array value MSB is set then increment if next byte's first two bits are 01

Notice that we can add a small value (1 or 2) to the counter and increment based on the next byte's masked value.