Поиск последовательной битовой строки 1 или 0

Как найти длину самой длинной последовательной битовой строки (1 или 0)?

00000000 11110000 00000000 00000000 → Если это 0, тогда длина будет 20

11111111 11110000 11110111 11111111 → Если это 1, тогда длина будет 12

Ответы

Ответ 1

Ниже приведено понятие о том, что если вы AND бит-последовательность со сдвинутой версией самого себя, вы эффективно удаляете трейлинг-1 из строки последовательных 1.

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

Повторение этого времени N приведет к уменьшению любой последовательности с N последовательными 1 до 0x00.

Итак, чтобы подсчитать количество последовательных 1:

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

Чтобы подсчитать количество последовательных 0, просто инвертируйте и одну и ту же процедуру.

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

Доказательство концепции: 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));
}

Вывод:

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

Ответ 2

Один простой способ состоял бы в том, чтобы просто перебрать биты и отслеживать количество бит в строке, имевших одно и то же значение, и максимум, достигший этого значения.

Здесь простая функция C, которая выполняет только это:

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 value */
        if(b == prevb) {
            cur += 1;
            if(cur > max)
                max = cur;
        }
        else {
            cur = 1; /* count self */
            prevb = b;
        }
    }
    return max;
}

Ответ 3

Вы можете сформировать таблицу поиска, чтобы сделать это быстро для вас. Чем больше таблица, тем быстрее выполняется поиск. Таблицы входа 2x256 могут выполнять 8 бит за раз с небольшим перекручиванием. Добавьте 1-ю версию таблицы и начните добавлять записи. Вероятно, я бы это сделал.

Ответ 4

Чтобы использовать идею таблицы, вам нужно что-то вроде

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;
}

инициализация таблицы выполняется прямолинейно, но зависит от вашего битового и байтового упорядочения (маленький конец или большой конец).

Ответ 5

Я не согласен с идеей таблиц, потому что я пытался это сделать и понял, что хотя "BA" в ASCII будет содержать 5 последовательных 0 для "B" и 5 последовательных 0 для "A", они не будут добавлять вместе для 10 последовательных 0. На самом деле, было бы 5 последовательных 0 максимум. (Это было связано с простым "счетным битом в идее таблицы". С тех пор Крис Додд разъяснил, как можно использовать таблицу точно.)

Я бы использовал такой алгоритм:

#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;
}

В этом алгоритме я предполагаю, что бит-поток представлен как 8-битные символы. Для каждого персонажа я смотрю на последний бит с поразрядным И. Если это то же самое, что и последний бит, тогда я подсчитываю количество последовательных бит, иначе я reset счет, потому что бит больше не последователен. Затем я использую операцию побитового сдвига, чтобы переместить следующий бит в символе для наблюдения. Надеюсь, это поможет!

Мой ответ - фактически дубликат ответа Дэвида Андерхилла.:)

Ответ 6

Поскольку вы не написали, что такое битовая строка (обычный int, байтовый массив или строка char, я предположил, что он 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;
}

Ответ 7

Проводка с iPhone с битыми пальцами.

Если они, то инвертировать.

Прокрутите ввод с помощью функции leadz. Для каждой итерации сдвиньте входной сигнал влево. Продолжайте, пока не дойдете до конца ввода. Обратите внимание, что вам нужно сравнить исходную длину ввода с суммарным числом счетчиков свинца.

Кроме того, в качестве оптимизации вы можете досрочно прервать, когда оставшаяся длина ввода меньше, чем самая большая запись, которую вы видели.

Есть много быстрых алгоритмов leadz онлайн.

Ответ 8

Если вы просто ищете байтовую строку из четырех байтов, вы можете упаковать их в unsigned long и использовать такой алгоритм:

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

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

    return k;
}

Для подсчета нулей, просто сначала получив побитовое дополнение.

Если вам нужно считать байтовые строки длиннее четырех, вы можете просто реализовать операции x >>= 1 и x & y либо непосредственно в байтовых строках, либо более эффективно использовать строки unsigned long, чтобы проверки переноса на реализацию x >>= 1 не слишком дороги.

Ответ 9

Это может помочь вам.... Сначала преобразуйте свой двоичный номер в биты строки. Это даст вам максимальное количество последовательных 1 (в java)

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