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\n", 0, count_consecutive_ones(0));
  printf("%d has %d consecutive 0's\n", 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\n", 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\n", 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

Answer 2

One simple way would be to simply loop over the bits, and keep track of the number of bits in a row which have had the same value, and the maximum that this value has reached.

Here's a simple C function which does just this:

int num_conseq_matching_bits(int n) {
    int i, max, cur, b, prevb;
    prevb = n & 1; /* 0th bit */
    cur = 1;
    max = 1;
    for(i=1; i<32; i++) {
        b = (n >> i) & 1; /* get the i'th bit's value */
        if(b == prevb) {
            cur += 1;
            if(cur > max)
                max = cur;
        }
        else {
            cur = 1; /* count self */
            prevb = b;
        }
    }
    return max;
}

Answer 3

You can form a look up table to do it quickly for you. The bigger the table, the faster the lookup. 2x256 entry tables can do 8 bits at a time with a little bit twiddling. Add a 1s version of the table and start adding entries. That's probably how I'd go about it.

Answer 4

To use the table idea, you need something like

static struct {
    int lead;  /* leading 0 bits */
    int max;   /* maximum 0 bits */
    int trail; /* trailing 0 bits */
} table[256] = { ....data.... };

int mostConsecutiveBits(unsigned char *str, int length, bool count_ones) {
    int max = 0; /* max seen so far */
    int trail = 0; /* trailing 0s from previous bytes */
    while (length-- > 0) {
        int byte = *str++;
        if (count_ones)
            byte ^= 0xff;
        if (table[byte].max > max)
            max = table[byte].max;
        if (trail + table[byte].lead > max)
            max = trail + table[byte].lead;
        if (byte)
            trail = table[byte].trail;
        else
            trail += 8;
    }
    return max;
}

initializing the table is straight-forward, but depends on your bit- and byte-ordering (little endian or big endian).

Answer 5

I don't agree with the tables idea, because I was trying it and realized that even though "BA" in ASCII would contain 5 consecutive 0's for 'B' and 5 consecutive 0's for 'A', they will not add together for 10 consecutive 0's. As a matter of fact, there would be 5 consecutive 0's maximum. (This was in reference to a simple "counting bits in a table idea." Chris Dodd has since expounded on how a table could be used accurately.)

I would use an algorithm like this:

#include <iostream>
#include <algorithm>

using namespace std;

// Assumes Little Endian architecture
int mostConsecutiveBits(char str[], int length) {
    int currentConsecutiveBits=0; 
    int maxConsecutiveBits=0; 
    char currentBit;
    char lastBit=0; 
    char currentChar=str[0];
    int charCtr,bitCtr; 

    for (charCtr=length-1; charCtr>=0; charCtr--) {

        currentChar=str[charCtr];

        for (bitCtr=0; bitCtr<8; bitCtr++) {
            currentBit=currentChar & 1;

            if (currentBit!=lastBit) {
                maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits);
                currentConsecutiveBits=1; 
                lastBit=currentBit;
            }
            else {
                currentConsecutiveBits++;
            }

            currentChar=currentChar>>1; 

        }
        maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits);
    }

    return maxConsecutiveBits; 
}   


int main (int argc, char * const argv[]) {
    cout << mostConsecutiveBits("AB",2);
    return 0;
}

In this algorithm, I assume the bitstream is represented as 8-bit characters. For each character, I look at the very last bit with a bitwise AND. If it's the same as the last bit, then I up the consecutive bit count, otherwise, I reset the count because the bits are no longer consecutive. I then use a bitwise shift operation to move the next bit in the character over for observation. Hope this helps!

My answer is effectively a duplicate of David Underhill's answer. :)

Answer 6

Since you didn't wrote what is bit string (regular int, byte array or char string I've assumed that it's char array

int maxConsBits(char *pStr,char cChar)
{
    char curChar;
    int curMax = 0;
    int max = 0;
    while (pStr)
    {
       if (*pStr == cChar)
       {
          curMax++;
          if (curMax > max)
          {
             max = curMax;
          }
       }
       else
       {        
           curMax = 0;
       }
       pStr++;
   }
   return max;
}

Answer 7

Posting from iPhone withbig fingers.

If ones, then invert.

Loop over the input using a leadz function. For each iteration, shift the input to the left. Continue until you reach the end of the input. Note that you need to compare the original input length with the cumulative leadz counts.

Also, as an optimization, you can early abort when the remaining input length is less than the largest leadz you have seen.

There are many fast leadz algorithms online.

Answer 8

If you're just looking for a byte string of four bytes, you can pack these into an unsigned long and use an algorithm like this:

int CountConsecutiveOnes(unsigned long n)
{
    unsigned long m = n;
    int k = 0;

    while (m)
    {
        ++k;
        n >>= 1;
        m &= n;
    }

    return k;
}

For counting zeros, just taking the bitwise complement first.

If you need to count byte strings longer than four, you can just implement the operations x >>= 1 and x & y either directly on the byte strings or it may be more efficient to use strings of unsigned long so the carry checks on the implementation of x >>= 1 aren't too expensive.

Answer 9

It may help you.... First convert your binary number to String say bits. It will give you max number of consecutive 1's (in java)

String[] split = bits.split("0");
Arrays.sort(split);
int maxLength = split[split.length - 1].length();

Answer 10

public static int maxConsecutiveOneInBinaryNumber(int number) {
int count = 0;
int max = 0;
while (number != 0) {
  if ((number & 1) == 1) {
    count++;
  } else {
    max = Math.max(count, max);
    count = 0;
  }
  number = number >> 1;
}
return Math.max(count, max);
}

You can this code here: https://github.com/VishalSKumar/DSFiddle/blob/master/src/main/java/com/vishalskumar/hackerrank/MaxConsecutiveOneInBinary.java