Search for the longest sequence of toggled consecutive bits in an integer

Question

I have to do a function ​called findsaw. This function searches for the longest sequence of toggled consecutive bits in an integer and returns the index of the first bit of the sequence, the sequence must start from the least significant bit.

In the case there are multiple answers(sequences with same size) choose the one with lowest start index.

Function signature:

unsigned int findsaw(int value)

Some test cases:

• findsaw(0x0) returns 0

• findsaw(0xAA) returns 0

• findsaw(0xA0F) returns 8

• findsaw(0xF0A) returns 0

• findsaw(0xFA0) returns 4

• findsaw(0xEAEA476BL) returns 23

My code:

#include <stdio.h>
#define YES 1 /* inside a sequence */
#define NO 0 /* outside a sequence */

unsigned int findsaw(int value){
    unsigned int sequence = value;
    unsigned char idx = 0;
    unsigned char sequenceIdx = 0;      
    unsigned char currentIdx = 0;      
    unsigned char size = 0;             
    unsigned char sequenceSize = 0;     
    unsigned char bit = value & 1;      
    unsigned char nextBit;              
    unsigned char insideSequence = NO;  


    while (sequence){   
        sequence>>= 1;
        nextBit = sequence & 1; 
        if(bit ^ nextBit){
            if(insideSequence){ 
                sequenceSize++;
            }
            else{
                sequenceSize = 2;
                sequenceIdx = currentIdx;
                insideSequence = YES;
            }
        }
        else{
            if(size < sequenceSize){
                size = sequenceSize;
                idx = sequenceIdx;
            }
            insideSequence = NO;
            sequenceSize = 0;
        }
        currentIdx++;
        bit = nextBit;
    }
    if(size < sequenceSize){
        idx = sequenceIdx;
    }
    return idx;
}

What would be the correct output for all 1's like findsaw(0xF), my function returns the index of the last bit, in this case 3?

Answer 1

Before we make any changes, let's add some tests to the end, so we have confidence that we don't break anything that worked:

#include <stdio.h>
static int test(unsigned int value, unsigned int expected)
{
    unsigned int actual = findsaw(value);
    if (actual == expected)
        return 0;
    printf("findsaw(%#x) = %u\n", value, actual);
    return 1;
}

int main()
{
    return test(0x0, 0)
        +  test(0xAA, 0)
        +  test(0x585, 0)
        +  test(0xA0F, 8)
        +  test(0xF0A, 0)
        +  test(0xFA0, 4)
        +  test(0xEAEA476Bu, 23);
}

This all passes (the program returns 0). I made test take the value as an unsigned int, because 0xEAEA476B is too big for a plain int on my system.

---

Now let's look at your code.

#include <stdio.h>
#define YES 1 /* inside a sequence */
#define NO 0 /* outside a sequence */

We're not using anything from <stdio.h>, so that's not required. Also, instead of defining YES and NO in the preprocessor, we could include <stdbool.h>, and then use true and false instead.

unsigned int findsaw(int value) {
    unsigned int sequence = value;

Are you required to accept input as a signed integer? If not, then declare findsaw() to take an unsigned int. As it is, the last test case (from the question's code) produced a compilation warning, as 0xEAEA476BL is larger than INT_MAX on my system.

unsigned char idx = 0;
unsigned char sequenceIdx = 0;
unsigned char currentIdx = 0;
unsigned char size = 0;
unsigned char sequenceSize = 0;
unsigned char bit = value & 1;
unsigned char nextBit;

None of these really need to be char. It's probably better to let them be int (or uint_fast8_t if you're really keen).

These names aren't immediately obvious to me (or to you in six months' time). It might be worth grouping them so that idx and size, which represent the best match so far, are placed together, with a comment explaining that. Similarly, sequenceIdx and sequenceSize seem to represent the current in-progress match, and should go together.

Some of the naming was alien to me: I'd have considered what you call the "next" bit to be "current", and what you call just "bit" to be "last_bit". That might be just me, though.

    if (bit ^ nextBit) {

A comment would be nice here: this is true when we're matching the sawtooth pattern. Also, the else branch contains actions that are only needed immediately at the end of a sequence, and do nothing for extended runs such as 0x00 or 0xFF, so that can be else if (insideSequence).

We can save a bit of work here:

        /* matched a transition */
        if (insideSequence) { /* just add to the size */
            sequenceSize++;
        } else {
            /* initialize for inside a sequence */
            sequenceSize = 2;
            sequenceIdx = currentIdx;
            insideSequence = true;
        }

If we initialise sequenceSize to 1 instead of 0, then we can simply increment it in both cases (i.e. outside the if). We can use sequenceSize == 1 to determine whether we're in a sequence, and we no longer need the insideSequence variable (nor <stdbool.h>):

unsigned int findsaw(unsigned int value) {
    unsigned int sequence = value;

    /* best match so far */
    unsigned int best_start = 0; /* this is what we're looking for */
    unsigned int best_size = 0;

    unsigned int sequenceIdx = 0;
    unsigned int currentIdx = 0;
    unsigned int sequenceSize = 1;


    while (sequence) {
        const int last_bit = sequence & 1;
        sequence >>= 1;
        const int current_bit = sequence & 1;
        if (last_bit ^ current_bit) {
            /* matched a transition */
            if (sequenceSize++ == 1) {
                /* the start of a new sequence */
                sequenceIdx = currentIdx;
            }
        } else if (sequenceSize != 1) {
            /* not matched - did we just finish a sequence? */
            if (best_size < sequenceSize) {
                best_size = sequenceSize;
                best_start = sequenceIdx;
            }
            sequenceSize = 1;
        }
        ++currentIdx;
    }
    if (best_size < sequenceSize) {
        best_start = sequenceIdx;
    }
    return best_start;
}

Let's see if we can do anything about the duplication of if (best_size < sequenceSize) when we reach the last bit. I'll add a couple of extra tests:

    +  test(0x50000005u, 27)
    +  test(0xA0000005u, 0)

The last one fails (returns 28), because we are zero-extending the left of the value, but not the right. If we simply take out the test, then other test cases fail (0xa0f and 0x50000005). It seems that the while (sequence) returns too early in those cases.

---

At this point, I give up fixing this and look at a different approach. We don't need to check last_bit ^ current_bit every time around the loop - we can compute them all at the same time like this:

unsigned int sequence = value;
unsigned int mask = sequence ^ (sequence >> 1);

This produces a 1 everywhere we have a bit preceded by its complement. We still have the problem that the high bit might be set, but we can fix this by writing mask = sequence ^ (sequence << 1) to make the low bit the stray one, and we can just shift that out. Now, all we have to do is find the longest run of 1s:

unsigned int findsaw(unsigned int value)
{
    unsigned int sequence = value;
    unsigned int mask = sequence ^ (sequence << 1);

    /* best match so far */
    unsigned int best_start = 0; /* this is what we're looking for */
    unsigned int best_size = 0;

    /* current run */
    unsigned int current_start = 0;
    unsigned int current_size = 0;

    /* current position */
    for (unsigned int i = 0;  mask >>= 1;  ++i) {
        if (mask & 1) {
            if (!current_size++)
                /* the start of a new run */
                current_start = i;
        } else if (current_size) {
            current_size = 0;
        }

        if (current_size > best_size) {
            best_size = current_size;
            best_start = current_start;
        }
    }

    return best_start;
}

#include <stdio.h>
static int test(unsigned int value, unsigned int expected)
{
    unsigned int actual = findsaw(value);
    if (actual == expected)
        return 0;
    printf("findsaw(%#x) = %u\n", value, actual);
    return 1;
}

int main()
{
    return test(0x0, 0)
        +  test(0xAA, 0)
        +  test(0x585, 0)
        +  test(0xA0F, 8)
        +  test(0xF0A, 0)
        +  test(0xFA0, 4)
        +  test(0xEAEA476Bu, 23)
        +  test(0x50000005u, 27)
        +  test(0xA0000005u, 0);
}

All the tests pass; time to go home.