-1

So I had an interview today, the question is:

Given a memory buffer, find a position of unset bit

int getPosition(const char *start, const int len)

If all bits in this memory buffer is 1, return -1

otherwise return an index of the unset bit, started from 0

Performance is first priority

Example

start, len=4
0x00|0x00|0x00|0x00: valid return: 0 to 31
0xFF|0xF0|0xFF|0xFF: valid return: 8,9,10,11
0xFF|0xFF|0xFF|0xFF: valid return: -1

Update Example

it does not have to be the leftmost or rightmost bit, any position as long as the bit is 0 is ok

00000000|00000000 : valid return 0 to 15
10101010|10101010 : valid return 0,2,4,6,8,10,12,14
11110111|11111111 : valid return 11

And my answer was

int getPosition(const char *start, const int len) {
    if(len<=0) return -1;
    int i;
    char *p;
    for(i=0;i<len*8;i++) {
      p = start + i/8;
      if(((*p) & (1<<(i%8)) == 0) return i; 
    }
}

but the interviewer said you have to loop many times if the last bit is 0, can you improve it?

I really do not know how to.

vego
  • 889
  • 1
  • 8
  • 20

1 Answers1

1

There's no need to test every single bit in a char that has all bits set, it will compare equal to (unsigned char)-1. With that and also taking into account that a char could have more than 8 bits, the following code should do the job:

#include <stdio.h>
#include <limits.h>

const char test[] = { 0xff, 0xf0, 0xff, 0xff };

long getpos(const char *buf, size_t len)
{
    size_t i;
    for (i = 0; i < len; ++i)
    {
        if ((unsigned char)buf[i] != (unsigned char)-1) break;
    }
    if (i == len) return -1;

    unsigned char x = buf[i];
    int bit = 0;
    while (x&1)
    {
        x >>= 1;
        ++bit;
    }
    return CHAR_BIT * i + bit;
}

int main(void)
{
    printf("%ld\n", getpos(test, sizeof test));
}