1 / 1 / 0
Регистрация: 23.08.2015
Сообщений: 7
|
||||||
1 | ||||||
Бинарный поиск флага02.12.2017, 22:33. Показов 2042. Ответов 12
Здравствуйте!
У меня такая задача: есть бинарный файл (вложен в архив к этому сообщению). Его надо считать в массив, а потом произвести бинарный поиск флага 01111110, который может начинаться в любой позиции байта. Считать в массив мне удалось (код приведен ниже), но я не понимаю, как можно провести поиск из середины байта (получается какое-то пересечение соседних байтов в массиве?) Например, фрагмент массива: 11100111 11100111 11100000 И то, что выделено жирным, должно быть найдено... Может, кто-то сталкивался с подобной задачей?
0
|
02.12.2017, 22:33 | |
Ответы с готовыми решениями:
12
Бинарный поиск Бинарный поиск Бинарный поиск Бинарный поиск На c# |
907 / 664 / 318
Регистрация: 23.10.2016
Сообщений: 1,543
|
||||||
03.12.2017, 12:15 | 2 | |||||
Поиск номера бита, с которого начинается совпадение
0
|
1142 / 851 / 262
Регистрация: 30.04.2009
Сообщений: 3,580
|
|
03.12.2017, 15:53 | 3 |
Сообщение было отмечено Nymeria как решение
Решение
Читаем по одному байту, запоминая предидущий байт.
Два байта складываем в Int16 (bytePrev << 8 | byteCurrent). Далее в цикле от 0 до восьми делаем сдвиг вправо и сравниваем младший байт с искомым. for (int i = 0; i<= 8; ++i) bool matched = (((byte)int16value >> i) & searchByte) == searchByte)
1
|
3458 / 2470 / 695
Регистрация: 02.08.2011
Сообщений: 6,692
|
|
03.12.2017, 16:11 | 4 |
А если биты начнут совпадать в младших трех битах 2-ого байта, и старших 5-ти битах 3-его байта? И т.д, с произвольным переходом через границу байтов.
0
|
1142 / 851 / 262
Регистрация: 30.04.2009
Сообщений: 3,580
|
|
03.12.2017, 18:42 | 5 |
На итерации, когда прочитали 3 байт, он сложится с предыдущим (2-ым), а дальше в цикле сдвига, когда i=3, младший байт int16value будет содержать нужное значение.
2
|
1 / 1 / 0
Регистрация: 23.08.2015
Сообщений: 7
|
||||||
04.12.2017, 22:45 [ТС] | 6 | |||||
nicolas2008, большое спасибо за Ваш ответ!
У меня вот такой цикл получился:
1
|
1142 / 851 / 262
Регистрация: 30.04.2009
Сообщений: 3,580
|
|
04.12.2017, 23:25 | 7 |
Nymeria, У вас почти все правильно сделано, я даже удивлен честно говоря
Во всех ваших попытках сформировать Int16 из двух байт вы делаете сдвиг в старший байт (<<8) значение типа byte, а в нем всего то 8 бит и сдвигать некуда. Нужно перед выполнением сдвига привести значение к типу Int16. short int16value = (((short)array[k-1]) << 8) | array[k]; Также не забудьте о крайнем случае, когда в массиве только 1 байт, его нужно проверять отдельно. А чтобы вообще все было идеально, избавьтесь от использования массива - делайте все в цикле чтения из BinaryReader. Но это потом, когда у вас будет рабочий вариант с массивом.
0
|
1 / 1 / 0
Регистрация: 23.08.2015
Сообщений: 7
|
|
04.12.2017, 23:39 [ТС] | 8 |
nicolas2008, спасибо! Дело в том, что мне дальше по задаче надо будет работать с массивом (считать байты между флагами, удалять байты и т.п.), поэтому от него не убежать
А насчет приведения, вот окончательный вариант этой строки, но ошибка та же: short int16value = (short)((((short)array[k - 1]) << 8) | (byte)array[k]); Я уже думаю, может, это связано с ArrayList?
0
|
1 / 1 / 0
Регистрация: 23.08.2015
Сообщений: 7
|
|
04.12.2017, 23:47 [ТС] | 9 |
Вот, что отображается.
Все-таки в ArrayList все записано корректно, но почему-то конвертировать в другие типы отказывается...
0
|
1 / 1 / 1
Регистрация: 18.10.2016
Сообщений: 9
|
|
05.12.2017, 07:15 | 10 |
Nymeria, массив типа string. Используй "Convert.ToInt16(string, 2);" для перевода в short.
0
|
1142 / 851 / 262
Регистрация: 30.04.2009
Сообщений: 3,580
|
|
05.12.2017, 07:35 | 11 |
Да, проблема в ArrayList.
В первом сообщении при добавлении в ArrayList байты конвертируются в string. ArrayList должен содержать элементи типа byte. Во вторых, в ArrayList для значимых типов (value type) делается boxing в обьект типа Object. Перед тем как начать работать с таким значением, ему нужно сделать unboxing в правильный тип, значение которого хранится в Object. В вашем случае происходит попытка unboxing в short в то время как на самом деле там находится не short, а string (или byte, если заполнение ArrayList уже исправлено). Вот так это делается: (short)(byte)array[k-1]. А лучще всего заменить ArrayList на List<byte>, который хранит типизированные значения, в таком случае не нужно будет такое двойное приведение типов.
2
|
1 / 1 / 0
Регистрация: 23.08.2015
Сообщений: 7
|
|
06.12.2017, 10:13 [ТС] | 12 |
nicolas2008, Да, со списком все заработало, спасибо!
Можно еще небольшой вопрос: после нахождения флагов, мне надо добавить в отдельные массивы (списки) байты, содержащиеся между каждыми двумя флагами. Но при этом мы производили побитовый сдвиг для обнаружения флага.. Как мне определить позиции начала и конца массива после флага?
0
|
1142 / 851 / 262
Регистрация: 30.04.2009
Сообщений: 3,580
|
|
07.12.2017, 01:36 | 13 |
Nymeria, Покажите как вы пытаетесь это сделать.
0
|
07.12.2017, 01:36 | |
07.12.2017, 01:36 | |
Помогаю со студенческими работами здесь
13
Бинарный поиск Поиск первого положительного элемента массива (бинарный поиск) Поиск заданного элемента в упорядоченном массиве (бинарный поиск) Поиск заданного элемента в упорядоченном массиве(бинарный поиск) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |