даны шесть бинарных строк (масок состояний), где 1 -- позиция _не_имеет_ значения (0/1), 0 -- однозначно определено. Код (Text): 101 101 101 111 000 111 101 001 111 101 100 111 111 100 101 111 001 101 надо найти минимальный алго перебора этих масок (прямой перебор не предлагать ).
Я правильно понимаю задачу, что мы рассматриваем только те биты, для которых во всех масках стоят единицы? Т.е. задача - найти все маски, в которых в качестве единичных битов могут быть только те, для которых все данные 6 масок содержат единицу? Правда, тогда непонятно, зачем целых 6 масок, если их все в одну можно объединить (поandить). Но если задача такая, то это известная задача на перебор всех подмасок данной маски, решается за O(ответа): Код (Text): for (int cur=msk-1; cur>0; cur=(cur-1)&msk) добавить_в_ответ_маску_cur; Здесь msk - это та маска, все подмаски которой надо получить. Нулевую подмаску надо добавить руками.
Код (Text): 101 101 101 111 000 111 101 001 111 101 100 111 111 100 101 111 001 101 на месте 0 -- значащие биты, на месте 111-ц -- незначащие (потому, что такие начальные условия, на месте значащих битов необходимо отлавливать "0"). данные (выровненные по 2 байта) хранятся в памяти, надо наименьшим кол-вом операций однозначно определить, проходят данные по маске(хотя бы по одной), или нет. P.S. регулярность появления каждой из масок одинакова, поэтому, думаю сначала проверять "серединный" бит. как-нибудь так: Код (Text): mov ax, [mem] and ax, 0x10 jnz @nea ... nea: P.P.S. и как быть, если вместо битов -- байты (0 / _не_0)?
если втупую, получается так: Код (Text): mov ax, [mem] and al, 0x10 jnz @nea shr al, 1 mov bl, al ;00110110 mov al, bl and al, 01001001b jnz @nea ;01100011 mov al, bl and al, 00011100b jnz @nea ;00100111 mov al, bl and al, 01011000b jnz @nea ;00110011 mov al, bl and al, 01001100b jnz @nea ;01110010 mov al, bl and al, 00001101b jnz @nea ;01100110 mov al, bl and al, 00011001b jnz @nea ... nea: если сразу избавиться от бита, который всегда "0", сжать сдвигами и инвертировать, тогда можно проверять по таблице... Код (Text): mov ax, [mem] not al shr al, 1 ; - mov bl, al and bl, 1 ; 1-разряд shr al, 1 and al, 0xE or bl, al and bl, 0xF ; 5,4,3,1-разряды shr al, 1 and al, 0x10 or bl, al and bl, 0x1F ; 7,5,3,1-разряды bt [table], bl jnc @nea ... nea: какие ещё предложения?
t00x А че так сложно, если только 7,5,3,1-разряды Код (Text): mov cl, [mem] test cl,10h jnz nea; and cl,10101010b jz ugu; mov al,cl shr cl,5 or cl,al mov ax,bitmask ;двоичная константа с учетом изменения порядка бит shr ax,cl jnc nea ugu:
leo так даже лучше (jz ugu; можно убрать)! Код (Text): mov cl, [mem] test cl,10h jnz nea; and cl,10101010b mov al,cl shr cl,5 or cl,al mov ax,bitmask ;двоичная константа с учетом изменения порядка бит shr ax,cl jnc nea ugu: 8 7 6 5 4 3 2 1 0
t00x Не понял. Если на заданных позициях д.б. нули, то cl = 0 удовлетворяет всем маскам, но никакого сдвига не производит и соотв-но CF не устанавливает. Поэтому если экономить на jz, то нужно инвертировать bitmask и юзать jc nea
leo всё верно. однако, cl = 0 (это не все, а ещё одна маска) -- её появление маловероятно, и тратить целый переход неэффективно. может предварительно установить CF, чтобы отлавливать этот случай? Код (Text): mov cl, [mem] test cl,10h jnz nea; and cl,10101010b mov al,cl shr cl,5 or cl,al mov ax,bitmask ;двоичная константа с учетом изменения порядка бит stc shr ax,cl jc nea ugu:
Ну, не-е Если cl=0 - маловероятно, то и переход jz практически всегда будет предсказываться верно и соотв-но команда jz будет "исполняться" (= "пропускаться") гораздо быстрее, чем тормозная stc. Тогда лучше делать как я выше сказал - инвертировать bitmask, чтобы на позициях, удовлетворяющих маскам, стояли нули, а не единицы, и соотв-но делать переход jc nea. В этом сл.после or cl,al флаг CF сам собой очищается и при cl=0 перехода не будет. PS: Вроде получается, что в упакованной 4-битной маске допускаются любые комбинации, содержащие 2 нуля. Поэтому значение bitmask для перехода по jc будет равно 111010001000000b Код (Text): mov cl, [mem] test cl,10h jnz nea; and cl,10101010b mov al,cl shr cl,5 or cl,al mov ax,111010001000000b ;если первые 4 бита cl содержат < 2-х нулей, то после shr ax,cl будет CF=1 shr ax,cl jc nea
Не понял, каких еще "троек" ? В маске #11 единицы стоят на запрещенных позициях, а все остальные являются разрешеными
leo значение bitmask не смотрел, однако: cl=0 - маловероятно, но вероятно и его необходимо обрабатывать отдельно в jxx nea, CF ведь не установлен при выполнении shr ax,cl P.S. "тройка" - 0001, 0010, 0100, 1000 после or cl,al
Установлен в 0 после or cl,al (о чем я собс-но уже сказал в #11) Все эти "тройки" являются допустимыми для твоих масок из #1 и уже учтены в bitmask = 111010001000000b (им соответствуют нули на соотв-х позициях: 0001 -> 0 в младшем разряде и т.д.)
Видимо, не понял Код (Text): or cl,al ;устанавливает CF=0 mov ax,111010001000000b shr ax,cl ;при cl=0 флаг CF не изменяется, т.е. остается CF=0 jc nea ;переход по CF=1 только для cl = 0111, 1011, 1110, 1101 и 1111 Вывод: Вариант #11 - вполне рабочий и ничего поправлять\добавлять в нем не нужно
