Odwzorowanie bitowe ciągu liczb z zakresu od 1 do 9999
sebcio_lcp
Program przedstawia jak w tablicy, która składa się z 313 elementów przechować 10000 liczb z zkresu od 1 do 9999. Program ma również możliwość zapisania tablicy do piku i odczytania jej z pliku. Plik ten jest plikiem tekstowym, do którego wpisujemy liczby wierszami (czyli każda wartość w osobnej linii). Cała zabawa polega na tym, że gdy podajemy jakąś liczbę np. 4 to jej postać binarna jest następująca 000000000000000000000000000000100, przy założeniu że przechowujemy liczby na 32 bitach. Wszystkie elementy tablicy zerujemy więc mają one postać 00000000000000000000000000000000. Teraz przy podaniu liczby 4 wybieramy odpowiednią komórkę tablicy, tworzymy "maskę" i używamy odpowiedniego opertora bitowego w tym przypadku "or == |". Operator ustawi nam czwarty bit pierwszego elementy tablicy. Aby sprawdzić czy dana liczba znajduje się w tablicy, trzeba użyć operatora "and == &" i sprawdzić czy czwarty bit jest jedynką.
Tworzenie maski:
-
Musimy stworzyc liczbe w takiej postaci binarnej 10000000000000000000000000000000. Robimy to w nastepujacy sposob ~0 (negacja zero), powoduje zanegowanie wszystkich zer w reprezentacji binarnej liczby zero. Czyli jest liczba zero ma postać 00000000000000000000000000000000 to po tej operacji otrzymamy 11111111111111111111111111111111. Teraz jesli przesuniemy w lewo 31 bitów tzn. wszystkie jedynki od prawej strony przesuwamy w lewo o 31 pozycji. Do tego celu uzyjemy operatora bitowego <<. Czyli jesli mamy zmienną mask i najpierw przypiszemy jej wartość zero mask = 0 potem mask = ~0 lub mask ~= 0 i wykonamy operacje przesunięcia mask = mask << 31 lub mask <<= 31 to otrzymamy maske w postaci 10000000000000000000000000000000
-
Pierwsza jedynka w naszej masce mozemy dowolnie manipulowac tzn. przesuwac ją na dowolną pozycję. W ten sposób tworzymy naszą maskę która ustawi nam odpowiedni bit w tablicy.
-
Jeśli mamy liczby 4 to ustawiamy czwarty bit. mask >>= 3 (wartosc - 1) i mamy maske 00010000000000000000000000000000
-
Bierzemy pierwszy element tablicy i używając operatora or ustawiamy 4 bit w tablicy:
tab[0]: 00000000000000000000000000000000
mask: 00010000000000000000000000000000
tab[0] | mask
lub
tab[0] or mask
tab[0]: 00010000000000000000000000000000
CDN...
Nie wiem czy ten program może się do czegoś przydać, dlatego proszę o uwagi. To jest mój pierwszy artykuł - bądźcie wyrozumiali :)
/* Odwzorowanie bitowe liczb *
* created by sebcio [[email protected]] *
* LCP 2004 *
*/
#include <stdio.h>
#include <stdlib.h>
#define INT_BITS (sizeof(unsigned int)*8)
#define TAB_SIZE ((10000 / INT_BITS)+1)
typedef enum {insert, check} IoC;
//protytpy (deklaracje) funkcji
char menu();
char InsertCheck(unsigned int *ptab, unsigned int data, IoC choice);
void zeros(unsigned int *ptab, int n);
void p(unsigned int d, char *name); //funkcja pomocnicza
char CheckTable(unsigned int *ptab);
void ShowAll(unsigned int *ptab);
void delete(unsigned int *ptab, unsigned int data);
void ReadFromFile(unsigned int *ptab);
void WriteToFile(unsigned int *ptab);
int main(int argc, char *argv[])
{
char c, result;
unsigned int tab[TAB_SIZE], *ptab = tab, data;
zeros(ptab,TAB_SIZE);
do {
c = menu();
switch (c) {
case 'l':
case 'L':
ReadFromFile(ptab);
break;
case 'z':
case 'Z':
WriteToFile(ptab);
break;
case 'W':
case 'w':
printf("\nPodaj liczbe: ");
scanf("%d", &data);
result = InsertCheck(ptab,data,check);
if (result != 0)
printf("\nBLAD: Podana liczba jest juz zarejestrowana ...\n");
else {
InsertCheck(ptab,data,insert);
printf("\nOK.\n");
}
break;
case 'O':
case 'o':
printf("\nJakiej liczby szukasz: ");
scanf("%d", &data);
result = InsertCheck(ptab,data,check);
if (result != 0)
printf("\nLiczba jest zarejestrowana ...\n");
else
printf("\nBrak szukanej liczby ...\n");
break;
case 'A':
case 'a':
if (CheckTable(ptab) == 1) {
printf("\nW bazie znajduja sie nastepujace liczby: ");
ShowAll(ptab);
}
else
printf("\nW bazie nie ma zadnej liczby ...\n");
break;
case 'U':
case 'u':
printf("\nPodaj liczbe do usuniecia: ");
scanf("%d", &data);
delete(ptab,data);
break;
case 'q':
case 'Q':
return 0;
default:
printf("\nBLAD: Nie ma takiej opcji ...\n");
break;
}
getchar();
} while (c != 'q' && c != 'Q');
return 0;
}
char menu()
{
char c;
printf("\n%20s%s\n", "","[L] - ladowanie dancyh z pliku");
printf("%20s%s\n", "","[Z] - zapis danych na plik");
printf("%20s%s\n", "", "[W] - wstawianie liczby do tablicy");
printf("%20s%s\n", "", "[O] - odczytywanie liczby z tablicy");
printf("%20s%s\n", "","[U] - usuwanie liczby z tablicy");
printf("%20s%s\n", "","[A] - automatyczne odczytanie zwartosci tablicy");
printf("%20s%s\n", "","[Q] - wyjscie z programu");
printf("\n%20s%s", "","Twoj wybor: ");
c = getchar();
return c;
}
char InsertCheck(unsigned int *ptab, unsigned int data, IoC choice)
{
unsigned int mask, nr, offset, count = 0;
nr = data / INT_BITS;
if (data % INT_BITS == 0)
--nr;
mask = ~0 << INT_BITS - 1;
offset = data - (INT_BITS * (data / INT_BITS));
if (offset == 0)
mask >>= INT_BITS - 1;
else {
--offset;
while (count != offset) {
mask >>= 1;
++count;
}
}
if (choice == insert)
*(ptab+nr) |= mask;
else
return (*(ptab+nr) & mask) != 0 ? 1 : 0;
}
void zeros(unsigned int *ptab, int n)
{
int i;
for (i = 0; i < n; ++i)
*(ptab+i) = 0;
}
void p(unsigned int d, char *name)
{
printf("\n");
printf("%s = ", name);
printf("%d", d);
}
char CheckTable(unsigned int *ptab)
{
unsigned int i, exist = 0;
for (i = 1; i < 10000; ++i)
if (InsertCheck(ptab,i,check) != 0) {
exist = 1;
break;
}
return exist;
}
void ShowAll(unsigned int *ptab)
{
unsigned int i;
for (i = 0; i < 10000; ++i)
if (InsertCheck(ptab,i,check) != 0)
printf("%d, ", i);
printf("\n");
}
void delete(unsigned int *ptab, unsigned int data)
{
unsigned int mask, nr, offset, count = 0;
if (InsertCheck(ptab,data,check) == 0)
printf("\nBLAD: Podana liczba nie jest zarejestrowana w bazie ...\n");
else {
nr = data / INT_BITS;
if (data % INT_BITS == 0)
--nr;
mask = ~0 << INT_BITS - 1;
offset = data - (INT_BITS * (data / INT_BITS));
if (offset == 0)
mask >>= INT_BITS - 1;
else {
--offset;
while (count != offset) {
mask >>= 1;
++count;
}
}
*(ptab+nr) &= ~mask;
printf("\nOK. Podana liczba zostala usunieta z bazy ...\n");
}
}
void ReadFromFile(unsigned int *ptab)
{
unsigned int liczba;
FILE *plik;
plik = fopen("tab.dat","r");
while (fscanf(plik,"%u",&liczba) != EOF) {
InsertCheck(ptab,liczba,insert);
}
fclose(plik);
}
void WriteToFile(unsigned int *ptab)
{
FILE *plik;
unsigned int i;
plik = fopen("tab.dat","w");
for (i = 1; i < 10000; ++i)
if (InsertCheck(ptab,i,check) != 0)
fprintf(plik,"%u\n",i);
fclose(plik);
}
Tak, masz racje. Cześć elementów jest nie wykorzystywana. A co do twojego kodu, to jeszcze niestety nie jestem na takim poziomie zaawansowania :) Ale dzięki będę miał co poanalizować w przerwie na kawę :) Pozdrawiam
Fajnie, ale stworzyleś tylko i wyłącznie odpowiednik pascalowego 'set of whatever', dodatkowo... Aby zakodować twoim sposobem 10000 liczb potrzeba ni mniej ni wiecej tylko 10000 bitów, czyli 10000/8=1250 bajtów. W jaki sposób udało ci sie skompresowac tą liczbe do 313 nie mam zielonego pojecia.
Całe ustawianie, gaszenie i czytanie bitów w buforze mozna zrobić na prawde prosto:
Pomijam brak tagów <cpp>
Ale o czym Ty tak naprawdę piszesz? Bo jakoś nie kumam po co to wszystko...
Poza tym po co robić mask = 0 skoro potem idzie mask = ~0 no ale lećmy dalej: chcesz uzyskać 1 na 32 bicie i robisz mask = ~0 i mask <<= 31 zamiast od razu mask = 1<<31.
Poza tym:
ustawiamy czwarty bit. mask >>= 3 i mamy maske 00010000000000000000000000000000
to nie 4 bit tylko 29 - czyli o indeksie 28. Czwarty bit (o indeksie 3) jest tu:
00000000000000000000000000001000
Co do tagów to niestety nie wiem co to jest. To mój pierwszy artykuł. Pisze w C od niedawna. Nie wiem może odwzorowanie bitowe może ma jakieś zastosowanie i komuś to co napisałem może się przydać. Chciałem jak najprościej opisać o co chodzi (dlatego między innymi pisałem mask = 0
). W kodzie już tego nie robiłem, chociaż nie jest on do końca optymalny można go uprościć.
Chodzi o to, że jeśli chcemy zapisać w tablicy liczbe np. 4 to ustawiamy czwaty bit. Wiem, że to jest 29 bit (jeżeli myślimi o kodowaniu liczb w naturalnym kodzie binarnym), ale nie chodzi nam tutaj o to, że najbardziej znaczący bit jest po lewej stronie. Chodzi o to, że te 32 bity to jest tak jakby "nasza pamięć". Ustawiając 4 bit od lewej strony, wiemy, że licba 4 została zapisana w tablicy. Można w ten sposób zaoszczędzić pamięci :) Nie trzeba tworzyć tablicy 10000 elementów typu int aby przechować jakieś wartości. Można stworzyć tablice 313 elementów i na podstawie tego czy odpowiedni bit jest ustawiony czy nie sprawdzać czy liczba znajduje się w tablicy.