1 / 1 / 0
Регистрация: 23.08.2015
Сообщений: 7
1

Бинарный поиск флага

02.12.2017, 22:33. Показов 2042. Ответов 12

Author24 — интернет-сервис помощи студентам
Здравствуйте!
У меня такая задача: есть бинарный файл (вложен в архив к этому сообщению). Его надо считать в массив, а потом произвести бинарный поиск флага 01111110, который может начинаться в любой позиции байта.
Считать в массив мне удалось (код приведен ниже), но я не понимаю, как можно провести поиск из середины байта (получается какое-то пересечение соседних байтов в массиве?)
Например, фрагмент массива: 11100111 11100111 11100000
И то, что выделено жирным, должно быть найдено...
Может, кто-то сталкивался с подобной задачей?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void PrintValues(IEnumerable myList)
        {
            foreach (Object obj in myList)
                Console.Write(" {0}", obj);
            Console.WriteLine();
        }
 
static void Main(string[] args)
        {
            string path = @"D:\Path\Example.bin";
            ArrayList array = new ArrayList();
            //string binary = "";
 
            using (BinaryReader reader = new BinaryReader(new FileStream(path, FileMode.Open)))
            {
 
                while (reader.BaseStream.Position < reader.BaseStream.Length)
                {
                    array.Add(Convert.ToString(reader.ReadByte(), 2));
                    //binary = Convert.ToString(reader.ReadByte(), 2);
                }
            }
            PrintValues(array);
 
            // Неудачные попытки сделать поиск через строку/регулярные выражения/просто по массиву
            //int countflag = new Regex("0111 1110").Matches(binary).Count; 
            //countflag = CountWords(binary,"01111110");
            //for (int i = 0; i < array.Count; i++)
            //{
            //    if ((string)array[i] == "0111 1110")
            //    {
            //        countflag++;
            //    }
            //}
            Console.ReadLine();
        }
Вложения
Тип файла: zip Example.zip (356.5 Кб, 2 просмотров)
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.12.2017, 22:33
Ответы с готовыми решениями:

Бинарный поиск
Доброе время суток! Подскажите пожалуйста, в чем заключается ошибка? иногда выводит все правильно, ...

Бинарный поиск
Элементы массивов вводятся пользователем вручную с клавиатуры. При вводе данных предусмотреть...

Бинарный поиск
Найти в массиве елемент со значением Х с помощью бинарного поиска. Добавлено через 1 минуту...

Бинарный поиск На c#
В институте сразу же начали писать на C#, конечно же, никто ничего не объяснил. Второй день мучаюсь...

12
907 / 664 / 318
Регистрация: 23.10.2016
Сообщений: 1,543
03.12.2017, 12:15 2
Поиск номера бита, с которого начинается совпадение
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
long Find(BinaryReader br, byte value)
{
    try
    {
        var next = br.ReadByte();
        int bytesRead = 1;
        if (next == value)
        {
            return 0;
        }
 
        var current = next;
        while (true)
        {
            next = br.ReadByte();
            bytesRead += 1;
            for (int offset = 1; offset <= 8; offset++)
            {
                current <<= 1;
                current |= (byte)((next >> (8 - offset)) & 1);
                if (current == value)
                {
                    return (bytesRead - 2) * 8 + offset;
                }
            }
        }
    }
    catch (EndOfStreamException)
    {
        return -1;
    }
}
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
Цитата Сообщение от nicolas2008 Посмотреть сообщение
Два байта складываем в Int16
А если биты начнут совпадать в младших трех битах 2-ого байта, и старших 5-ти битах 3-его байта? И т.д, с произвольным переходом через границу байтов.
0
1142 / 851 / 262
Регистрация: 30.04.2009
Сообщений: 3,580
03.12.2017, 18:42 5
Цитата Сообщение от IamRain Посмотреть сообщение
А если биты начнут совпадать в младших трех битах 2-ого байта, и старших 5-ти битах 3-его байта? И т.д, с произвольным переходом через границу байтов.
Цитата Сообщение от nicolas2008 Посмотреть сообщение
Читаем по одному байту, запоминая предидущий байт.
На итерации, когда прочитали 3 байт, он сложится с предыдущим (2-ым), а дальше в цикле сдвига, когда i=3, младший байт int16value будет содержать нужное значение.
2
1 / 1 / 0
Регистрация: 23.08.2015
Сообщений: 7
04.12.2017, 22:45  [ТС] 6
nicolas2008, большое спасибо за Ваш ответ!
У меня вот такой цикл получился:
C#
1
2
3
4
5
6
7
8
9
10
11
for (int k = 1; k < array.Count; k++)
            {
                // пробовала short int16value = (short)((byte)array[k - 1] << 8 | (byte)array[k]); - не сработало
                // пробовала short int16value = Convert.ToInt16(((byte)array[k - 1] << 8 | (byte)array[k])); - не сработало
                int int16value = ((byte)array[k - 1] << 8 | (byte)array[k]);
                for (int i = 0; i <= 8; ++i)
                {
                    bool matched = ((((byte)int16value >> i) & searchByte) == searchByte);
                    Console.WriteLine(matched);
                }
            }
Подскажите, пожалуйста, как грамотно задать тип/конвертировать в Int16? У меня после разных способов появляется ошибка "Заданное приведение является недопустимым"...
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.12.2017, 01:36
Помогаю со студенческими работами здесь

Бинарный поиск
Как осуществить бинарный поиск, например числа 27. Как это работает понимаю, но не могу написать...

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

Поиск заданного элемента в упорядоченном массиве (бинарный поиск)
Заполнить одномерный массив из n элементов согласно таблицы. Размерность массива задать в виде...

Поиск заданного элемента в упорядоченном массиве(бинарный поиск)
Заполнить одномерный массив из n элементов по формуле приведенной в картинке. Размерность массива...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru