|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
11.06.2015, 08:21 | #1 | |
Участник клуба
Регистрация: 11.01.2010
Сообщений: 1,139
|
Поиск подстроки битов в 1024-битовой строке
Наткнулся на достаточно интересное "студенческое" задание
Цитата:
|
|
11.06.2015, 10:34 | #2 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Как-то не понял сам алгоритм, но если это биты, то что мешает делать сравнение по маске, сдвигать регистр и опять сравнивать?
I'm learning to live...
|
11.06.2015, 11:13 | #3 |
Участник клуба
Регистрация: 11.01.2010
Сообщений: 1,139
|
Здравствуйте, Stilet!
если делать сравнения по маске, сдвигать и опять сравнивать, то для поиска 6 разрядов в 1024-разрядной строке потребуется 1024-6=1018 сравнений в худшем случае, хотелось бы чего-нибудь более быстрого. Например, потратить 1024/6=170 сравнений в худшем случае |
11.06.2015, 11:25 | #4 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Стоп, а речь идет не о самом решении, а о нахождении наиболее шустрого алгоритма?
I'm learning to live...
|
11.06.2015, 12:48 | #5 |
C/C++, Asm
Участник клуба
Регистрация: 02.03.2010
Сообщений: 1,323
|
Stilet дело говорит.
Код:
(бит-стрим читается справа-налево) // последние 8 байт непроверенными получились, можно сделать еще один цикл без LODSB и r8 = 8 Последний раз редактировалось f.hump; 11.06.2015 в 13:13. |
11.06.2015, 14:53 | #6 | |
Участник клуба
Регистрация: 11.01.2010
Сообщений: 1,139
|
Цитата:
допустим, подстрока начинается с нуля, составляем массив индексов положения нулей в 1024-строке, подставляем подстроку к каждому нулю и проверяем на совпадение со следующим от нуля битами, ну это так, на уровне бреда |
|
11.06.2015, 19:20 | #7 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Цитата:
I'm learning to live...
|
|
12.06.2015, 14:03 | #8 |
Участник клуба
Регистрация: 11.01.2010
Сообщений: 1,139
|
Stilet,
это также на уровне бреда, здесь в поисковой подстроке на 6 бит соотношение нулей и единиц 0,5; делим 1024-строку на участки по 6 бит и смотрим соотношение нулей и единиц, если больше или меньше - пропускаем |
12.06.2015, 20:19 | #9 |
Участник клуба
Регистрация: 16.06.2011
Сообщений: 1,428
|
..сори, но для чего может понадобится поиск 6-битного значения?!
Если это маска, то должна быть минимум 8 бит (с нулями впереди), а так - где можно применить значение в 6-бит? Просто интересно..
Нашедшего выход - затаптывают первым..
|
12.06.2015, 20:24 | #10 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Чё-чё чё? Ещё раз, подробнее. . Ой. Уже умираю от смеха.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
поиск подстроки в строке С | pepsik66 | Помощь студентам | 10 | 12.11.2012 19:25 |
поиск подстроки в строке | Aina Utebekova | Помощь студентам | 27 | 11.10.2012 04:24 |
поиск подстроки в строке | Pozitiffe | Общие вопросы C/C++ | 5 | 18.02.2012 21:48 |
Поиск подстроки в строке | videolord | Общие вопросы по Java, Java SE, Kotlin | 2 | 10.04.2011 09:11 |
поиск подстроки в строке!!! | StoneSour | Общие вопросы C/C++ | 2 | 15.03.2010 21:31 |