VPF::биты в байты и обратно %) - Форум программистов

boostcoder

Дата 26.5.2012, 23:30 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

всем привет!

снова мне повстречалась задача с битами smile

прошу помощи.

имеем класс, описывающий битовое множество(QBitArray)
нужно это дело поместить в массив байт, и обратно.

я не очень-то понимаю как мне итерироваться по битам каждого байта массива.

спасибо.

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

boostcoder

Дата 26.5.2012, 23:48 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

в общем, нагуглил два решения:
http://stackoverflow.com/questions/8776261...y-to-qbytearray
http://stackoverflow.com/questions/5251403...on-of-stdbitset

и сразу понял как реализовать задачу smile

(еще бы)))

но решение для QBitArray что-то мне кажется дико оверхедным...
у кого-то есть предложения по оптимизации?

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

volatile

Дата 27.5.2012, 00:15 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(boostcoder @ 26.5.2012, 23:48

)

но решение для QBitArray что-то мне кажется дико оверхедным...

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

А вот исправить баг, в первом линке, не помешает

Цитата

bytes.resize(bits.count()/8);

Если кол-во битов не кратно 8, то программка сильно обломится.
нужно как-то так:

Цитата

bytes.resize((bits.count() + 7)/8);

boostcoder

Дата 27.5.2012, 00:22 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(volatile @ 27.5.2012, 00:15

)

А вот исправить баг, в первом линке, не помешает

о, спасибо smile

ладно, вопрос закрываю.

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

volatile

Дата 27.5.2012, 00:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Кстати там ниже, это испривили, (только что посмотрел)

Цитата

bytes.resize(bits.count()/8+1);

Но все равно, мой вариант, более точный:

Цитата(volatile @ 27.5.2012, 00:15

)

bytes.resize((bits.count() + 7)/8);

mes

Дата 27.5.2012, 00:52 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 26.5.2012, 22:48

)

у кого-то есть предложения по оптимизации?

написать Qt, зато что лишила доступа к внутренней прослойке smile

ведь могла б возвращать data (), как ByteArray...

--------------------

http://opendots.net

boostcoder

Дата 27.5.2012, 01:04 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

mes, а ведь в стандартной реализации этого тоже нет: http://en.cppreference.com/w/cpp/utility/bitset

Добавлено через 2 минуты и 50 секунд
и в boost.dynamic_bitset этого тоже нет, почему-то.

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 27.5.2012, 09:02 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 27.5.2012, 00:04

)

этого тоже нет: http://en.cppreference.com/w/cpp/utility/bitset

ага, там ограничились u(l)long'ом... сам не так давно возмущался их поведением smile

Добавлено через 3 минуты и 20 секунд

Цитата(boostcoder @ 27.5.2012, 00:04

)

и в boost.dynamic_bitset этого тоже нет, почему-то.

там хоть to_block_range есть smile

--------------------

http://opendots.net

boostcoder

Дата 27.5.2012, 12:19 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(mes @ 27.5.2012, 09:02

)

там хоть to_block_range есть

да, точно

Цитата(mes @ 27.5.2012, 09:02

)

там ограничились u(l)long

Вы про то, что внутреннее хранилище состоит из массива long`ов?

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 27.5.2012, 12:45 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 27.5.2012, 11:19

)

Вы про то, что внутреннее хранилище состоит из массива long`ов?

про возвращение набора битов как u(l)long, размера которого увы не всегда хватает..а о массиве они почему то не подумали..

--------------------

http://opendots.net

boostcoder

Дата 27.5.2012, 13:00 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

ааа, ну да.
но раз уж все известные мне реализации поступают так же, возможно есть на то причина?

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 27.5.2012, 13:24 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 27.5.2012, 12:00

)

но раз уж все известные мне реализации поступают так же, возможно есть на то причина?

как выяснили не все.. а причина думаю только одна, непонятка зачем при работе с битами массив байтов хранилища.. smile

--------------------

http://opendots.net

boostcoder

Дата 27.5.2012, 13:27 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

ясно)

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

borisbn

Дата 27.5.2012, 13:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

у всех этих "стандартных" битсетов (что std, что boost, что Qt) есть один недостаток: они складывают биты в байте начиная с младшего.
Например, последовательность 10101100 будет равна 0x35, а многие библиотеки (да почти все) требуют, чтобы биты складывались, начиная со старшего бита. Т.о. приведённая последовательность должна быть равна 0xAC, а не 0x35.
Так что советую реализовать свой битсет (можно без блекджека))). Тем более, что это - совсем нетрудно

Это сообщение отредактировал(а) borisbn - 27.5.2012, 13:58

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

hawk3500

Дата 29.5.2012, 16:45 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 246
Регистрация: 6.2.2009

Репутация: нет
Всего: 2

Занимаюсь ЦОС. На ПК более быстрого и прозрачного решения чем ниже описанное не нашёл.
Да не экономично по отношению к памяти , зато быстро и прозрачно.

Код


//Класс для распаковки битов
bool BIN_GO2[256][8];
int GetBitFromBuff(char buff,int n)
{
    return (buff&(1<<((n%8))))!=0;
}
clsBlock::clsBlock(void ) 
{
    // Подготовка к работе, инициализация переменных
char V;
for(int i=0;i<256;i++)
{
    V=char(i);
    BIN_GO2[i][0]=bool(GetBitFromBuff(V,0));
    BIN_GO2[i][1]=bool(GetBitFromBuff(V,1));
    BIN_GO2[i][2]=bool(GetBitFromBuff(V,2));
    BIN_GO2[i][3]=bool(GetBitFromBuff(V,3));
    BIN_GO2[i][4]=bool(GetBitFromBuff(V,4));
    BIN_GO2[i][5]=bool(GetBitFromBuff(V,5));
    BIN_GO2[i][6]=bool(GetBitFromBuff(V,6));
    BIN_GO2[i][7]=bool(GetBitFromBuff(V,7));
}
}

void clsBlock::CharToBit(unsigned char *IN_MASS,bool *OUT_MASS,int In_Mass_Lenght)
{
    int next_position=0;
    int current_byte=0;
    int tmp=0;
    int byte_size=8*sizeof(bool);
    memset(OUT_MASS,0,In_Mass_Lenght*sizeof(bool));
    while(current_byte<In_Mass_Lenght)
    {
        tmp=int(IN_MASS[current_byte]);
        memcpy(&OUT_MASS[next_position],&BIN_GO2[tmp][0],byte_size);
        next_position+=8;
        current_byte++;
    }
return;
}







//класс для упаковки

bool BIN_GO2[256][8];
char PARSE[2][2][2][2][2][2][2][2];
int GetBitFromBuff(char buff,int n)
{
    return (buff&(1<<((n%8))))!=0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
// Конструктор класса
clsBlock::clsBlock(void )
    // Подготовка к работе, инициализация переменных

char V;
for(int i=0;i<256;i++)
{
    V=char(i);
    BIN_GO2[i][0]=bool(GetBitFromBuff(V,0));
    BIN_GO2[i][1]=bool(GetBitFromBuff(V,1));
    BIN_GO2[i][2]=bool(GetBitFromBuff(V,2));
    BIN_GO2[i][3]=bool(GetBitFromBuff(V,3));
    BIN_GO2[i][4]=bool(GetBitFromBuff(V,4));
    BIN_GO2[i][5]=bool(GetBitFromBuff(V,5));
    BIN_GO2[i][6]=bool(GetBitFromBuff(V,6));
    BIN_GO2[i][7]=bool(GetBitFromBuff(V,7));
}

for(int j=0;j<256;j++)
{
    PARSE[!!BIN_GO2[j][0]][!!BIN_GO2[j][1]][!!BIN_GO2[j][2]][!!BIN_GO2[j][3]][!!BIN_GO2[j][4]][!!BIN_GO2[j][5]][!!BIN_GO2[j][6]][!!BIN_GO2[j][7]]=char(j);
}

}


void clsBlock::BitToChar(bool *IN_MASS,char *OUT_MASS,int In_Mass_Lenght)
{
    int OUT_POS=0;
    int loacl_lenght=In_Mass_Lenght/8;
    for(int i=0;i<loacl_lenght;i++)
    {
        OUT_MASS[i]=PARSE[!!IN_MASS[OUT_POS]][!!IN_MASS[OUT_POS+1]][!!IN_MASS[OUT_POS+2]][!!IN_MASS[OUT_POS+3]][!!IN_MASS[OUT_POS+4]][!!IN_MASS[OUT_POS+5]][!!IN_MASS[OUT_POS+6]][!!IN_MASS[OUT_POS+7]];
        OUT_POS+=8;
    }
return;    
}

Это сообщение отредактировал(а) hawk3500 - 29.5.2012, 16:54

--------------------

воин dzen'a

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »