Найдите шаблон двоичных чисел, используя сдвиг вправо и побитовый - И?

StackOverflow https://stackoverflow.com/questions/818800

Вопрос

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

Пример:
Делает 100111 содержать 1001?

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

Итак, в моей голове я подумал, что это подойдет:

100111 AND 1001 = 0  
Shift-right 1  
010011 AND 1001 = 0  
Shift-right 1  
001001 AND 1001 = 1 // Pattern FOUND!

и повторяйте это до тех пор, пока либо число не будет сдвинуто до тех пор, пока оно не станет равным нулю, либо И не вернет 1.

Тем не менее, я думаю, что, должно быть, я что-то перепутал, потому что это возвращает 1 для большинства вещей, которые я ввел, при первом запуске цикла.Я запутался в своем использовании И?

Это было полезно?

Решение

Проблема в том, что "частичные совпадения" также возвращают ненулевое значение для вашего И проверяют:

100111 AND 001001 = 000001

Итак, это проверяет, если Любой из битов совпадают, но вы хотите убедиться, ВСЕ биты те же самые.Результат И должен быть равен шаблону, который вы ищете:

x = 100111
if (x AND 1001 == 1001)
  print "found"

Другие советы

Вы должны И и затем протестировать шаблон поиска:

if ((TestPattern & SearchPattern) == SearchPattern)
{
   // then match
}

(где & представляет побитовое AND)

Побитовый И работает не так, как вы ожидаете (судя по примерам и игнорируя обозначения, которые, по-видимому, предполагают, что вы используете побитовый И в качестве логического И битов).И "принимает во внимание" только те биты, которые установлены равными 1.Например, 1111 И 1001 == 1001.

Вам нужно использовать XOR и сравнить с 0 для совпадения (помните, что маскируйте биты, которые вы не сравниваете, из результата).В вашем примере совпадение найдено, когда (N ^ 1001) & 1111 == 0000

Чтобы убедиться, что оба бита 0 и 1 соответствуют вашему шаблону поиска, вам нужно сделать что-то вроде этого:

if ((InputPattern AND SearchMask) == SearchPattern)
{
    // then match
}

В SearchMask должно быть всего 1 бит, длина которого равна вашему searchPattern.Например, вы могли бы иметь SearchMask == 1111, SearchPattern == 1001.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top