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

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

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

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

Следующее основано на понятии, что если вы 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 

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

Вот простая функция 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; } 

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

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

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

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

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

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

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

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

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

В Интернете есть много быстрых алгоритмов leadz.

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

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

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

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

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

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

 int CountConsecutiveOnes(unsigned long n) { unsigned long m = n; int k = 0; while (m) { ++k; n >>= 1; m &= n; } return k; } 

Для подсчета нhive, сначала возьмем побитовое дополнение.

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

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

 String[] split = bits.split("0"); Arrays.sort(split); int maxLength = split[split.length - 1].length(); 
 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

  • n & (n-1), что делает это выражение?
  • Использование \ b и \ r в C
  • Как я могу написать общий class контейнера, который реализует данный интерфейс в C #?
  • Где используется ключевое слово C auto?
  • хранение денежных сумм в mysql
  • Присвоение строк массивам символов
  • Как получить знак, мантисса и показатель числа с плавающей запятой
  • Разница между char a = "string"; char * p = "string";
  • Что такое блок C # Using и почему я должен его использовать?
  • Почему мой оператор мощности (^) не работает?
  • Странное предупреждение компилятора C: предупреждение: «struct» объявлен в списке параметров
  • Interesting Posts

    c #, ‘Forms’ не существует в пространстве имен system.windows

    Сделать WPF Image load async

    Потерянное место на диске в Windows 7 не может найти недостающее

    Не удается получить местоположение и электронную почту с помощью API Facebook

    Вызов сканера штрих-кода при нажатии кнопки в приложении Android

    В андроидном приложении Toolbar.setTitle метод не действует – имя приложения отображается как заголовок

    Как вы убиваете Thread в Java?

    Использование true и false в C

    Есть ли способ сделать мой жесткий диск недоступным для всех, кроме меня?

    Найти текстовую строку с помощью jQuery?

    Что означает статус = отменен для ресурса в средствах разработчика Chrome?

    Код ошибки: 1005. Невозможно создать таблицу «…» (errno: 150)

    Нет типов Spring WebApplicationInitializer, обнаруженных на пути к classам

    Доступ к определенному полю в произвольно вложенных данных JSON

    Преобразование кассетной записи в цифровой формат

    Давайте будем гением компьютера.