Odwzorowanie bitowe ciągu liczb z zakresu od 1 do 9999

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:

1. 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

2. 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.

3. Jeśli mamy liczby 4 to ustawiamy czwarty bit. mask »= 3 (wartosc - 1) i mamy maske 00010000000000000000000000000000

4. 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 [sebcio@e7.pl]        *
 *        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);
}

Kategoria: C » Artykuły

4 komentarze

Brak avatara
Napisany 2004-12-11 11:31 przez sebcio_lcp

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

Avatar: flabra
Napisany 2004-12-10 18:25 przez flabra

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:

int getbit(void* buf,unsigned long bit){
  return ((((char*)buf)[bit>>3]>>((bit&7)))&1);
}

void setbit(void*  buf,ulong bit){
  ((char*)buf)[bit>>3]|=1<<(bit&7);
}

void clearbit(void*  buf,ulong bit){
  ((char*)buf)[bit>>3]&=(~(1<<(bit&7)));
}

// i dwie powyzsze razem z zabezpieczeniem na 1 bit
void changebit(void*  buf,ulong bit,int newstate){
  (((char*)buf)[bit>>3]&=(~((newstate=(!!newstate))<<(bit&7))))|=(newstate<<(bit&7));
}

Avatar: Marooned
Napisany 2004-12-08 00:12 przez Marooned

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ć <b>mask = 0</b> skoro potem idzie <b>mask = ~0</b> no ale lećmy dalej: chcesz uzyskać 1 na 32 bicie i robisz <b>mask = ~0</b> i <b>mask <<= 31</b> zamiast od razu <b>mask = 1<<31</b>.

Poza tym:
<i>ustawiamy czwarty bit. mask >>= 3 i mamy maske 00010000000000000000000000000000</i>
to nie 4 bit tylko 29 - czyli o indeksie 28. Czwarty bit (o indeksie 3) jest tu:
00000000000000000000000000001000

Brak avatara
Napisany 2004-12-08 21:16 przez sebcio_lcp

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.

Facebook
4programmers.net