Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Битовый массив

Автор: kutuzov 19.1.2007, 15:43

Добрый день У меня есть массив битов. char * mask; mask = new char[MaskSize]; Надо написать функцию, вырезаюшую из массива биты от m до n (размер массива естественно уменьшается) т.е. Пишу функцию CutMask(m,n) Не очень у меня получается что-то ... может кто подскажет как ?? Неплохо бы на примере...

Автор: Anikmar 19.1.2007, 15:53

Т.е. если я правильно понял - этот массив рассматривается как длиннющая последовательность битов? Или каждый символ представляет собой представления битов?

Автор: JackYF 19.1.2007, 16:10

Anikmar, я так понял - все таки второе.. Вопрос на засыпку - MaskSize > 4 или нет? От этого, как мне кажется - много чего зависит...

Автор: Frage 19.1.2007, 16:28

Без пояснения решения не найти - если MaskSize==3, то мask массив из 3-х бит или 24? А удалять что-либо можно только перекопировав содержимое в новую строку, убив старую

Автор: kutuzov 19.1.2007, 16:56

Цитата(Anikmar @ 19.1.2007,  15:53) Т.е. если я правильно понял - этот массив рассматривается как длиннющая последовательность битов? Или каждый символ представляет собой представления битов? Рассматривается как последовательность битов.  т.е. есть некий список элементов. Информация о том использовать их или нет сохраняется в массив. таким образом, например: есть 12 элементов. из них установлены только первый и 3й. Битовый массив из 2х байтов. массив будет выгладить так:  10100000 00000000 (т.к. установлены только 1й и 2й элемент) Добавлено @ 17:00  Цитата(Frage @ 19.1.2007,  16:28) Без пояснения решения не найти - если MaskSize==3, то мask массив из 3-х бит или 24? А удалять что-либо можно только перекопировав содержимое в новую строку, убив старую MaskSize==3 то массив из 8 бит(1 байт). как создать массив из 3х бит, а уж тем более записать можно я не знаю...

Автор: GIK 19.1.2007, 17:26

А не легче тогда создать структуру?  Если нужно использовать массив, и при этом динамически удалять эллементы, то можно использовать вектор.

Автор: zkv 19.1.2007, 17:32

задача учебная? Если нет то, думаю, std::vector<bool> тебе поможет

Автор: Earnest 19.1.2007, 17:35

Лучше std::bitset

Автор: zkv 19.1.2007, 17:46

Цитата(Earnest @  19.1.2007,  17:35 ) Лучше std::bitset вроде не стыкуется с  Цитата(kutuzov @  19.1.2007,  15:43 ) (размер массива естественно уменьшается) Цитата(MSDN) Describes a type of object that stores a sequence consisting of a fixed number of bits

Автор: cia 19.1.2007, 18:33

А много ли элементов в массиве? Если не очень много, то может проще было бы использовать все-таки 1 байт = 1 биту (флагу) ? Тогда функция будет заключаться в копировании части строки "из середины в начало" и уменьшении ее длины. zkv, поочередно удалить каждый элемент?

Автор: Rockie 19.1.2007, 18:59

Цитата(kutuzov @  19.1.2007,  16:56 ) 10100000 00000000 (т.к. установлены только 1й и 2й элемент) хмм, всмысле нулевой и второй? или первый и третий.. а биты ты считаешь слева направо? Цитата(kutuzov @  19.1.2007,  15:43 ) Надо написать функцию, вырезаюшую из массива биты от m до n (размер массива естественно уменьшается)т.е. Пишу функцию CutMask(m,n) можешь привести пример исходных данных и результата работы функции?

Автор: kutuzov 19.1.2007, 19:08

Цитата(cia @ 19.1.2007,  18:33) А много ли элементов в массиве? Если не очень много, то может проще было бы использовать все-таки 1 байт = 1 биту (флагу) ? Тогда функция будет заключаться в копировании части строки "из середины в начало" и уменьшении ее длины. zkv, поочередно удалить каждый элемент? элементов много. Если битовый массив, то примерно 1Мб выходит. Если для каждого флажка использовать не бит а байт уже не метр получается  - потери памяти - скорости - и плюс ко всему конфиг 1 Мб или 8 мб читать/писать 2 больше разницы... Добавлено @ 19:12  Цитата(Earnest @ 19.1.2007,  17:35) Лучше std::bitset Пробовал через bitset перегонять... const int Mask1Size=OldSize; bitset<Mask1Size> bOld; получаю Template argument must be a constant expression т.е. на сколько понял размер надо задавать при компиляции...

Автор: zkv 19.1.2007, 19:31

Цитата(kutuzov @  19.1.2007,  19:08 ) Если битовый массив, то примерно 1Мб выходит. Если для каждого флажка использовать не бит а байт уже не метр получается smile std::vector<bool> - массив битов, а не байтов Цитата(„Новые сложные задачи на C++ Автор: Герб Саттер.") Попытка №2: использование стандартного контейнера упакованных битов Вторая идея заключается в том, чтобы обратить внимание на то, что стандартная библиотека уже содержит два контейнера для хранения битов: bitset и vector<bool>. Для наших целей bitset — плохой вариант, поскольку bitset<N> имеет фиксированную длину N, а мы должны работать с потоками битов переменной длины. Не получается… Зато vector<bool>, несмотря на все его недостатки в данном случае оказывается тем, что доктор прописал

Автор: Anikmar 19.1.2007, 20:33

Цитата(zkv @  19.1.2007,  19:31 ) std::vector<bool> - массив битов, а не байтов Цитата(„Новые сложные задачи на C++ Автор: Герб Саттер.") Попытка №2: использование стандартного контейнера упакованных битов Вторая идея заключается в том, чтобы обратить внимание на то, что стандартная библиотека уже содержит два контейнера для хранения битов: bitset и vector<bool>. Для наших целей bitset — плохой вариант, поскольку bitset<N> имеет фиксированную длину N, а мы должны работать с потоками битов переменной длины. Не получается… Зато vector<bool>, несмотря на все его недостатки в данном случае оказывается тем, что доктор прописал Интересно, если STL - шаблонные классы, то как они реализовали в одном шаблоне и биты и другие типы? т.е. vector<int> и  vector<bool> получается разные шаблоны? Я думал, что шаблонный класс реализован одинаково с точки зрения внутренних конструкций... template class<T> Т.е. получается, что конкретно для класса bool меняется реализация? Ведь нет типа данных Бит?

Автор: zkv 19.1.2007, 20:42

Цитата(Anikmar @  19.1.2007,  20:33 ) Ведь нет типа данных Бит?   я о нем, во всяком случае,  ничего не знаю  Цитата(Anikmar @  19.1.2007,  20:33 ) Я думал, что шаблонный класс реализован одинаково с точки зрения внутренних конструкций... template class<T> примечание к предыдущей цитате  Цитата(„Новые сложные задачи на C++ Автор: Герб Саттер.") (Конечно, стандарт не требует, чтобы реализация vector<bool> использовала упакованные биты, а только поощряет это. Тем не менее большинство реализаций именно так и поступают.) Ссылка на эту главу есть в закрепленной теме форума

Автор: MAKCim 19.1.2007, 20:47

Цитата Т.е. получается, что конкретно для класса bool меняется реализация? Ведь нет типа данных Бит? ключевые слова: специализация шаблона

Автор: Anikmar 19.1.2007, 21:00

Цитата(MAKCim @  19.1.2007,  20:47 ) ключевые слова: специализация шаблона  Это об чем? Мне действительно непонятна реализация такого шаблона. Если я хочу написать свой шаблонный класс, который по-разному бы реагировал на тип в аргументе? Например пишу шаблон: Код template <class T> class Mas10 {    T Temp[10]; // Куча полезных методов } И если я хочу, чтобы мой класс по-разному отреагировал на конкретный тип данных, то каким путем это решено в vector<bool>? Повторяю: мне просто занятно стало. Это действительно как-то решено или это пожелания Герба Саттера?

Автор: MAKCim 19.1.2007, 21:24

Anikmar,  Код template<> class Mas10<bool> {     bool Temp[10]; ... };

Автор: zkv 19.1.2007, 21:28

Цитата(Anikmar @  19.1.2007,  21:00 ) Это действительно как-то решено или это пожелания Герба Саттера?   скорее пожелания стандарта. Цитата(Anikmar @  19.1.2007,  21:00 ) Мне действительно непонятна реализация такого шаблона. мне тоже, но я не расстраиваюсь  (меня больше интересует практическая часть), но если бы мне вдруг захотелось разобраться, то я начал бы, пожалуй, с изучения файла vector

Автор: Anikmar 19.1.2007, 21:41

Цитата(zkv @  19.1.2007,  21:28 ) то я начал бы, пожалуй, с изучения файла vector  А вы туда заглядывали? Там достаточно много всего наверчено, я туда естественно заглянул перед тем как отправить свой пост.  Если есть обсуждаемая тема, и есть люди, которые уже в этом разбирались - какой смысл перелопачивать кучу хедеров? Это чисто познавательный интерес - я не доходил в реализации собственных шаблонных классов до "перегрузки" с точки зрения типов - форум для того и существует, чтобы делиться опытом. Вариант определения шаблона, показанный в посте MAKCim меня просветил (я так ни разу не делал). НО... Тогда получается дублирование всех методов в двух разных шаблонах для обеспечения работы с конкретными типами данных... На самом деле в векторе немного не так сделано - там маленький служебный класс, отвечающий за выделение памяти и обращение к конкретному элементу видимо отрабатывает что-то отдельное для bool. Но сходу не нашел где. ИМХО Я и так не особый любитель STL. Но посмотрев конкретику реализации vector у меня появились сомнения, что использование STL приведет к ускорению работы программы и к экономии памяти... Вот к экономии времени на исходный код - возможно.

Автор: Rockie 19.1.2007, 23:51

Цитата(Anikmar @  19.1.2007,  21:41 )  у меня появились сомнения, что использование STL приведет к ускорению работы программы и к экономии памяти... Вот к экономии времени на исходный код - возможно. все зависит от того кто и как пишет то или иное. Цитата(Anikmar @  19.1.2007,  21:41 ) Если есть обсуждаемая тема, и есть люди, которые уже в этом разбирались Вот и были люди(и щас есть) которые в свое время очень долго и нудно разбирались, создавая STL и добиваясь наилучшей реализации, причем по многим критериям.

Автор: zkv 20.1.2007, 06:57

Цитата(Anikmar @  19.1.2007,  21:41 ) На самом деле в векторе немного не так сделано - там маленький служебный класс, отвечающий за выделение памяти и обращение к конкретному элементу  , да, и совсем "небольшая" подборка базовых алгоритмов    Цитата(Anikmar @  19.1.2007,  21:41 ) ИМХО Я и так не особый любитель STL. Но посмотрев конкретику реализации vector у меня появились сомнения, что использование STL приведет к ускорению работы программы и к экономии памяти... к ускорению по сравнению с чем? Цитата(Anikmar @  19.1.2007,  21:41 ) Вот к экономии времени на исходный код - возможно.  экономия времени по сравнению с чем? недостаток любой универсализации - дополнительные расходы ресурсов, плюсы известны. невозможно определить эффективность универсального подхода (опять таки по сравнению с другим методом) не зная условия задачи

Автор: Anikmar 20.1.2007, 11:49

Цитата(zkv @  20.1.2007,  06:57 ) по сравнению с чем? На круг - по сравнению с "ручным" написанием. В большинстве случаев ведь не надо самому реализовывать низкоуровненвые алгоритмы и т.п. - для этого, например, придумана IDE - которая служит для ускорения написания интерфейса и многих других вещей. Я ни коим образом не хочу принизить достоинства STL - ее писало очень много народу и очень долго. Этот вопрос я поднял чисто из интереса самообразования - из цикла "Как оно сделано" - интересно все-таки. Любой универсализм естественно тратит рессурсы. (Взять, например, технологию COM). Конкретно задачи, указанной в данном топике, vector<bool> подоходит как нельзя лучше, не знаю на счет критерий скорости (нужна ли там супер высокая скорость или нет). А по поводу моего личного "прохладного" отношения к STL - это чисто ИМХО. Видимо сказывается то, что начинал я на очень скромных рессурсах - приходилось, в основном, программировать контроллеры АСУ, а там рессурсов было ну очень мало. Цитата(zkv @  20.1.2007,  06:57 ) да, и совсем "небольшая" подборка базовых алгоритмов Я не говорю про простоту класса vector. Я говорю про подход, указанный MAKCimом, когда он мне объяснил как разделить шаблоны для разных типов. Если делать разные объявления vectora для разных типов - было бы совсем соложно. Разработчики несколько упростили и вынесли типозависимые участки в маленькие служебные классы с 2 методами (их так проще сопровождать). Резюме: век живи - век учись. Правда все равно дураком помрешь

Автор: zkv 20.1.2007, 13:18

Цитата(Anikmar @  20.1.2007,  11:49 ) Я не говорю про простоту класса vector. Я говорю про подход, указанный MAKCimом, Anikmar, виноват, не внимательно прочитал ваш пост, теперь понял о чем речь. Мои извинения.   Цитата(Anikmar @  20.1.2007,  11:49 ) А по поводу моего личного "прохладного" отношения к STL - это чисто ИМХО. Видимо сказывается то, что начинал я на очень скромных рессурсах - приходилось, в основном, программировать контроллеры АСУ, а там рессурсов было ну очень мало. не в обиду, вспоминается герой рассказа Д. Лондона "Любовь к жизни", который довольно долгое время голодал, и потом когда его подобрали собирал сухари под матрацем  Нет я не отрицаю, бывают "голодные" ситуации когда приходится учитывать каждый "сухарь" , но в большинстве задач такая экономия, пожалуй, будет смотреться как паранойя.

Автор: Anikmar 20.1.2007, 13:35

Цитата(zkv @  20.1.2007,  13:18 ) но в большинстве задач такая экономия, пожалуй, будет смотреться как паранойя.  Полностью с этим согласен!

Автор: The Thing 20.1.2007, 16:45

Специально для автора темы потратил 15 минут. Массив рассматривается как непрерывный поток данных с лево направо.  Вывод на экран до и после вырезания битов: ------------------------------- 11101100 11100000 11101100 11100000 00100000 11101100 11111011 11101011 11100000 00100000 11110000 11100000 11101100 11110011  11101100 11101111 10111110 10111110 00000010 00001111 00001110 00001110 11001111 00110000  ------------------------------- Код #include <math.h> #include <iostream> #include <conio.h> using namespace std; class CWorBit {     char m_str[100];     size_t m_length; public:     CWorBit()     {         strcpy_s(m_str, "мама мыла раму"); //строка которая выводится         m_length = strlen(m_str);     }     void Display()     {         size_t pos=0;         for(;pos<m_length; pos++){             unsigned char _posBit=128;             for(;; _posBit/=2){                 cout << bool(m_str[pos]&_posBit) << flush;                 if(_posBit == 1)                     break;             }             cout << " " << flush;         }     }     void SetBit(size_t Idx, bool zn);     bool GetBit(size_t Idx);     void CutMusk(size_t m, size_t n); }; //получить бит bool CWorBit::GetBit(size_t Idx) {     unsigned char posBit_beg = 128;     size_t pos=0;     for(; pos<size_t(double(Idx%8)+0.0001); pos++)         posBit_beg = posBit_beg/2;     return (bool)(m_str[Idx/8]&posBit_beg); } //поставить бит void CWorBit::SetBit(size_t Idx, bool zn) {     unsigned char posBit_beg = 128;     size_t pos=0;     for(; pos<size_t(double(Idx%8)+0.0001); pos++)         posBit_beg = posBit_beg/2;     if(zn)         m_str[Idx/8] = m_str[Idx/8]|posBit_beg;     else{         if(m_str[Idx/8]&posBit_beg)             m_str[Idx/8] = m_str[Idx/8]^posBit_beg;     } } //Вырезать кусок void CWorBit::CutMusk(size_t m, size_t n) {     if(m >=n || n > m_length*8){         cerr << "CutMusk error m=" << m << " n=" << n << flush;         return;     }          bool bit=0;     size_t pos=n, erase_beg = m; //нужный нам бит     for(;pos<m_length*8; pos++){         bit = GetBit(pos); SetBit(erase_beg++, bit);     }     pos = erase_beg; //обрезаем массив     for(;pos<m_length*8; pos++){         SetBit(pos, 0);     }     m_length = strlen(m_str); //изменяем длину } void main(void) {     CWorBit wbit;     wbit.Display();     cout << endl;     wbit.CutMusk(12, 48);     wbit.Display();     getch(); } А всем вышекомментирующим: не надо лениться написать три строчки кода. Вся программа заключается в функциях Get и SetBit.  Добавлено @ 16:49  счет битов с нуля

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)