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

Question

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

00000000 11110000 00000000 00000000 -> Если оно равно 0, длина будет 20

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

Answer 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

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

Answer 3

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

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

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

Answer 5

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

Вы можете этот код здесь: https://github.com/VishalSKumar/DSFiddle/blob/master/src/main/java/com/vishalskumar/hackerrank/MaxConsecutiveOneInBinary.java

Answer 6

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

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

Answer 7

Если вы просто ищете байтовую строку из четырех байтов, вы можете упаковать ее в 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 не слишком дороги.

Answer 8

Отправка с iPhone большими пальцами.

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

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

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

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

Answer 9

Поскольку вы не написали, что такое битовая строка (обычный int, байтовый массив или символьная строка, я предположил, что это массив символов

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 10

Я не согласен с идеей таблиц, потому что я пробовал ее и понял, что хотя «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-битных символов. Для каждого символа я смотрю последний бит с побитовым AND. Если он совпадает с последним битом, то я увеличиваю количество последовательных битов, в противном случае я сбрасываю счет, потому что биты больше не являются последовательными. Затем я использую операцию побитового сдвига, чтобы переместить следующий бит в символе для наблюдения. Надеюсь, это поможет!

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