Как организовать побитовую запись?

Question

[Евгений Трофимов]

Пытаюсь реализовать алгоритм Хаффмана, который будет сжимать текстовый файл. Уже построено дерево tree, у которого есть:
tree->simvol // char в котором хранится сам символ (например 'a')
tree->code // string, двоичный код для этого символа (например 1001)

Мне нужно написать функцию, которая пройдется по исходному файлу, и будет считывать каждый символ, сверяя его с символами в моем дереве, а найдя нужный - запишет в новый файл последовательность единиц и нулей(tree->code).

Трудность именно в побитовой записи, т.к я не совсем представляю, как ее организовать. Поясню - мне нужно, чтобы ,например, последовательность 10011110 занимала именно 8 бит, т.е единица или ноль занимали бы 1 бит, иначе сжатия не получится(если я просто вместо буквы "а" запишу "1001" как набор символов, а не битов).

void shifr(){
	ifstream myfile("file.txt");//открыли файл
	char ch;
	if (!myfile.is_open()) // если файл не открыт
     	   cout << "Файл не может быть открыт!\n"; // сообщить об этом
	else
	{
		while (myfile.get(ch))//проходимся посимвольно по всему текстовому файлу
		{
		find_char(ch);//находим нужный символ в дереве и записываем код этого символа в новый файл
		}	
		myfile.close();
	}
}

void find_char(spisok *&tree, char ch) {//рекурсивный обход дерева и поиск в нем символа
	if (tree->left==NULL && tree->right==NULL && tree->simvol==ch) {
		//???
		//вот тут нужно как-то записать код из tree->code в новый файл...
		//???
	}
	if (tree->left!=NULL) {
		find_char(tree->left,ch);
	}
	if (tree->right!=NULL) {
		find_char(tree->right,ch); 
	}
}

Answer 1

[Андрей Инишев]

Можно создать переменную типа char и переключать в ней отдельные биты с помощью побитового или

char result = 0;
// допустим, что код - 8 бит
for (char* x = tree->code, int y = 0; *x != '\0'; x++, y++)
    if (*x == '1')
        *x |= 1 << (8 - y);

Answer 2

[Евгений Трофимов]

В общем очень много где искал и в итоге нашел несколько способов, хотя как по мне все они не особо удобные.
Надеюсь помогу кому-нибудь, а то сам довольно долго разбирался что да как.

Самая простая - создать структуру байта и описать в ней каждый бит.
Причем максимально верно, как я понял, так это сделать это через объединения, хотя я еще не совсем в этом разобрался.

struct Bits
{
    unsigned b0:1, b1:1, b2:1, b3:1, b4:1, b5:1, b6:1, b7:1;
};
union CBits
{
    Bits bits;
    unsigned char byte;
};

В этом случае записать 1 байт можно например вот так -

void write_bait(FILE* out, string code) { 
	CBits byte;
	byte.bits.b0=(code[0]=='1') ? 1:0;//тоже самое что и if(code[0]=='1') byte.bits.b0=1; else byte.bits.b0=0;
        .................
	byte.bits.b7= (code[7]=='1') ? 1:0;
	fwrite(&byte,sizeof(one_byte),1,out);
}

Второй способ - преобразовать массив boolean в unsigned char и "побитовым или" писать в нужный бит 1
Если я правильно понял - c = c | (1 << 7); - это запись в 7-й разряд, т.е
00000000
00000010
____________
00000010
и с = 2^7 = 128

а
(c & (1<<7)) != 0) - это проверка на 1 в 7-м разряде
т.е
00000111
00000010
___________
00000010
результат !=0, значит есть единица в 7-м разряде.

void BoolToByte(FILE *file, bool b[8])
{
    unsigned char c = 0;
    for (int i=0; i < 8; ++i)
        if (b[i])
		{
            c = c | (1 << i);
		}
    fwrite(&c,1,1,file);
    return;
}

и

void BoolFromByte(FILE *file, bool b[8])
{
	unsigned char c;
	fread(&c,1,1,file);
    for (int i=0; i < 8; ++i)
		if ((c & (1<<i)) != 0) b[i] = true;
}

Мне же удобно было держать коды в string , поэтому я переделал под нее -

void ToByte(FILE *file, string &b)
{
    unsigned char c = 0;
    for (int i=0; i < 8; ++i) 
		{
			if (b[i]=='1') 
			{
				c = c | (1 << i);
			}
		}
    fwrite(&c,1,1,file);
    return;
}

и

void FromByte(FILE *file , string &b)
{
	unsigned char c;
	fread(&c,1,1,file);
    for (int i=0; i < 8; ++i)
		if ((c & (1<<i)) != 0) b[i] = '1';	
}

Еще есть вариант, но я до него не дошел - это писать все непосредственно в буфер, а потом записывать весь буфер целиком, а не по байтам, как я.

В общем как-то так, поправьте меня, если где ошибся или можно улучшить/сократить функцию..

Answer 3

[AtomKrieg]

1) Пишите байты в vector<bool> (решение тривиально)
2) Пишите vector<bool> в файл (решение есть в интернете)

Answer 4

[mikhail_404]

И никогда не используйте
std::vector <bool>
alenacpp.blogspot.ru/2005/06/vector.html
Совет #18 (Мейерс)!
Можно, например, в инте все хранить или, на крайний случай, std::bitset.

Comments

[AtomKrieg]

Где написано "никогда не используйте!11" ?

[mikhail_404]

AtomKrieg: это рекомендация, к которой стоит прислушаться. Почитать можно по ссылкам. Если они не смогут Вас убедить, то у меня других аргументов не будет)