c - Finding consecutive bit string of 1 or 0

Question

How to find the length of the longest consecutive bit string(either 1 or 0)?

00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20

11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12

Answer 1

The following is based on the concept that if you AND a bit sequence with a shifted version of itself, you're effectively removing the trailing 1 from a row of consecutive 1's.

      11101111   (x)
    & 11011110   (x << 1)
    ----------
      11001110   (x & (x << 1)) 
        ^    ^
        |    |
   trailing 1 removed

Repeating this N times will reduce any sequence with N consecutive 1's to 0x00.

So, to count the number of consecutive 1's:

int count_consecutive_ones(int in) {
  int count = 0;
  while (in) {
    in = (in & (in << 1));
    count++;
  }
  return count;
}

To count the number of consecutive 0's, simply invert and the same routine.

int count_consecutive_zeros(int in) {
  return count_consecutive_ones(~in);
} 

---

Proof of concept: http://ideone.com/Z1l0D

int main(void) {
  printf("%d has %d consecutive 1's
", 0, count_consecutive_ones(0));
  printf("%d has %d consecutive 0's
", 0, count_consecutive_zeros(0));

  /* 00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20 */
  printf("%x has %d consecutive 0's
", 0x00F00000, count_consecutive_zeros(0x00F00000));

  /* 11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12 */
  printf("%x has %d consecutive 1's
", 0xFFF0F7FF, count_consecutive_ones(0xFFF0F7FF));
}

Output:

0 has 0 consecutive 1's
0 has 32 consecutive 0's
f00000 has 20 consecutive 0's
fff0f7ff has 12 consecutive 1's