tags:

views:

228

answers:

7

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

+6  A: 

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;
}
David Underhill
Why the downvote?
David Underhill
@David Underhill . I did the downvote. I have since undone the downvote. It's not that I doubt the accuracy of the solution, it's just that it seems unhelpful. I assume that anybody asking this question is easily able to implement a correct, but very slow, solution themselves. I suspected the questioner needs something fast.But now I'm not so sure.So, I'll think I'll hold my fire for now, and neither upvote nor downvote.
Aaron McDaid
Fair enough. Since the question didn't ask for a fast solution, I just went with a simple and straightforward one. Correctness first :).
David Underhill
+2  A: 

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.

Michael Dorgan
A: 

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. :)

froggythefrog
He has a char array of bytes, probably each byte is either '0' or '1', allowing you to make your solution even shorter.
earlNameless
Oops.... forgot, of all things, to actually keep track of the biggest number of consecutive 0's, so I added in max_consecutive0s. This is the value you'd want to return, print, etc.
froggythefrog
@earlNameless: But then what fun would it be without bitwise operations? :)
froggythefrog
@froggythefrog, true, I'd give up some sanity for fun
earlNameless
@froggythefrog your logic fails for the below.{ 0x01, 0xff, 0x00, 0xff } should return 9 { 0x00, 0x01, 0xff, 0xff } should return 17are u assuming little endian or big endian?
bithacker
@bithacker Doh! I see the problem. I am traversing the characters in the wrong order, so despite the fact I am looking at the bits in each character from right to left, I am traversing the characters from right to left. With my next edit, my code sample will have a for loop that traverses the characters from length-1 to 0. I wrote this program and ran it on a couple of Intel i586's, which are little endian. I was assuming that the leftmost bit would carry over the one on a right-shift.
froggythefrog
That was "characters from left to right"
froggythefrog
+1  A: 

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).

Chris Dodd
A: 

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;
}
XAder
A: 

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.

No One in Particular
A: 

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.

Charles Bailey