C operacje na bitach - upchanie dwóch zmiennych do jednej

Witam,

Dziś na wykładzie profesor poruszył ciekawy temat. Mając dwie zmienne, których wartość spokojnie zmieści się na 4 bitach nie ma sensu tworzyć dwóch charów, tylko jeden i na pierwszych 4 bitach upchać pierwszą wartość, na drugich czterech drugą stosując operatory bitowe. Chciałbym się bliżej przyjrzeć tej czynności. Jest jakaś fachowa nazwa takiej praktyki? Szukam w internecie coś na ten temat, ale nie wiem jak zapytać google ;)

Fachowa nazwa: "Przesunięcia bitowe".

lekcja na dziś: pola bitowe aka bitfield -> http://en.cppreference.com/w/cpp/language/bit_field wtedy nie trzeba sie bawić w ręczne przesunięcia bitowe.
Ale poza bardzo szczególnymi sytuacjami nie ma to sensu. Szczególne sytuacje kiedy sie to robi to np. transmisje danych z sond kosmicznych, gdzie przepustowość jest mocno ograniczona i trzeba kompresować dane tak jak się da. W zwykłych zastosowaniach jest to słabe bo procesor nie potrafi operować na takich małych jednostkach tylko na całych rejestrach, więc nawet jeśli masz 1 bit danych to procesor będzie pracował przynajmniej na 8 bitach.

można to łatwo osiągnąć

masz dwie zmienne a i b, chcesz umieścić każdą na 4 bitach w jednej zmiennej 8 bitowej c;:

unsigned char c = ((a<<4)&0xF0) | (b&0x0F) ;

jeżeli a i b są typu unisigned to wystarczy
unsigned char c = ((a<<4)) | (b) ;

odzyskanie wartości:
b = c & 0xF;
a = (c>>4) & 0xF;

Powinno być ok. Można też użyć do tego struktur/unii. W c++ jeszcze dochodzi bitstream.

Owszem, stosuje się technikę przesunięć bitowych, oraz pól bitowych. Trzeba jednak wiedzieć że dostęp do takiego pola z zasady jest wolniejszy (bo kompilator sam przesuwa/maskuje bity aby wydobyć lub zapisać to co nas interesuje), rzutowanie z innego typu łamie często strict aliasing i ogólnie, jak się zerknie co "wydziwia" kompilator w asemblerze... to się z tego rezygnuje i przesuwa/maskuje się w kodzie bezpośrednio.
Pola bitowe niestety w standardzie C i C++ nie mają zdefiniowanej kolejności. Bit o indeksie zero może wypaść w innym miejscu w kompilatorze X i w innym w Y.
A co do sztuczek bitowych to warto kilka poznać choćby tu: https://graphics.stanford.edu/~seander/bithacks.html lub z książki https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685 . Można dzięki nim np. szybko wyliczać parzystości, ilości bitów zapalonych/zgaszonych, testować czy liczba jest potęgą 2'ki czy wydobyć najmłodszy zapalony bit.

Wyżej jest "prosto", tutaj jest "skomplikowanie":

typedef struct packed
{
    char a : 4;
    char b : 4;
} packed;

i użycie

packed foo;
foo.a = 7;
foo.b = 3;
assert(sizeof foo == 1);

W c++ ze strukturami trzeba uważać, np ten kod:

 
// Example program
#include <iostream>
#include <string>

struct A {

  //bitmap file header (14 bytes)
  char Sign1,Sign2; //2
  unsigned int File_Size; //4
  unsigned int Reserved_Dword; //4
  unsigned int Data_Offset; //4

  //bitmap info header (16 bytes)
  unsigned int Dib_Info_Size; //4
  unsigned int Image_Width; //4
  unsigned int Image_Height; //4

  unsigned short Planes; //2
  unsigned short Bits; //2  
};

int main()
{
  std::string name;
  std::cout << sizeof(A)<<std::endl;
}

wklejony do http://cpp.sh/ zwraca 32 a nie 30 :)

I jeszcze ciekawe zastosowanie pakowania liczb do optymalizacji kodu:

#include <iostream>
#include <sys/time.h>

unsigned char* test;

unsigned int size = 1024 * 1024 * 200;

long ms() {
	struct timeval tp;
	gettimeofday(&tp, NULL);
	return tp.tv_sec * 1000 + tp.tv_usec / 1000;
}

long bitOptTest(unsigned char* test) {
	long start1 = ms();
	unsigned int *t = (unsigned int*)test;
	for(int i=0;i<size/4; i++) {
		t[i] = 0x19191919;
	}
	
	unsigned long sum = 0;
	for(int j=0; j<100; j++) {
		for(unsigned int i=0; i<size/4; i++) {
			unsigned int v = t[i];
			sum += ((v>>24)&0xFF) + ((v>>16)&0xFF) + ((v>>8)&0xFF) + (v&0xFF);
		}
	}
	long end1 = ms();
	std::cout<<sum<<std::endl;
	
	return (end1-start1);
}

long simpleSumTest(unsigned char* test)  {
	long start2 = ms();
	for(unsigned int i=0; i<size; i++) {
		test[i] = 25;
	}
	
	unsigned long sum = 0;
	for(int j=0; j<100; j++) {
		for(unsigned int i=0; i<size; i++) {
			sum += test[i];
		}
	}
	long end2 = ms();
	std::cout<<sum<<std::endl;
	return (end2-start2);
}

int main(int argc, char* argv[]) {
	test = new unsigned char[size];
	
	long time1 = bitOptTest(test);
	long time2 = simpleSumTest(test);
	
	std::cout<<"BIT OPTIMAL 1: "<<time1/1000.0<<std::endl;
	std::cout<<"SIMPLE SUM  2: "<<time2/1000.0<<std::endl;

	delete[] test;
	
	return 0;
}

Wynik dla O2 i O3 :

$ c++ -O2 main.cpp -o main
$ ./main.exe
524288000000
524288000000
BIT OPTIMAL 1: 5.734
SIMPLE SUM 2: 8.84

$ c++ -O3 main.cpp -o main
$ ./main.exe
524288000000
524288000000
BIT OPTIMAL 1: 2.618
SIMPLE SUM 2: 5.593