C/C++ Bit Array lub Bit Vector

Question

Uczę się programowania w języku C/C++ & napotkałem użycie "Bit bit arrays" lub "Bit Vectors". Nie jestem w stanie zrozumieć ich celu? tutaj są moje wątpliwości -

1. Czy są używane jako flagi boolowskie?
2. Czy zamiast tego można użyć tablic int? (więcej pamięci oczywiście, ale ..)
3. Co to za koncepcja Bit-Maskowania?
4. Jeśli maskowanie bitowe to proste operacje na bitach, aby uzyskać odpowiednią flagę, w jaki sposób program dla nich? czy nie jest trudno wykonać tę operację w głowie, aby zobaczyć, jaka będzie flaga, w stosunku do liczb dziesiętnych?

Szukam aplikacji, dzięki czemu mogę lepiej zrozumieć. na przykład -

Q. Dostajesz plik zawierający liczby całkowite z przedziału (od 1 do 1 miliona). Istnieje kilka duplikatów, a więc brakuje niektórych numerów. Znajdź najszybszy sposób na znalezienie brakujących numerów ?

Dla powyższego pytania, przeczytałem rozwiązania, które zalecają mi użycie tablic bitowych. W jaki sposób jeden przechowywać każdą liczbę całkowitą w nieco?

Answer 1

Chyba masz się mylić między tablicami i cyfr, a konkretnie co to znaczy manipulować liczb binarnych.

Pójdę o tym za pomocą przykładu. Załóżmy, że masz kilka komunikatów o błędach i chcesz zwrócić je w zwracanej wartości z funkcji. Teraz możesz oznaczyć swoje błędy 1,2,3,4 ... co ma sens w twoim umyśle, ale w jaki sposób, biorąc pod uwagę tylko jeden numer, można ustalić, które błędy wystąpiły?

Spróbuj teraz opisać błędy 1,2,4,8,16 ... zwiększając moce dwojga. Dlaczego to działa? Cóż, kiedy pracujesz w bazie 2, manipulujesz liczbą taką jak 00000000, gdzie każda cyfra odpowiada potędze 2 pomnożonej przez jej pozycję od prawej. Powiedzmy, że występują błędy 1, 4 i 8. Cóż, może to być reprezentowane jako 00001101. W odwrotnej kolejności pierwsza cyfra = 1 * 2^0, trzecia cyfra 1 * 2^2 i czwarta cyfra 1 * 2^3. Dodanie ich wszystkich daje 13.

Teraz jesteśmy w stanie sprawdzić, czy taki błąd wystąpił poprzez zastosowanie maski bitowej. Na przykład, jeśli chcesz się dowiedzieć, czy wystąpił błąd 8, użyj reprezentacji bitowej 8 = 00001000. Teraz, w celu wydobycia, czy nie, że wystąpił błąd, należy użyć binarny i tak:

00001101 
& 00001000 
= 00001000 

Jestem pewien, że wiesz, w jaki sposób działa i czy można go wywnioskować z powyższego - cyfra mądry pracy jeśli jakieś dwie cyfry są zarówno 1, wynik jest 1, w przeciwnym wypadku 0.

teraz w C:

int func(...) 
{ 
    int retval = 0; 

    if (sometestthatmeans an error) 
    { 
     retval += 1; 
    } 


    if (sometestthatmeans an error) 
    { 
     retval += 2; 
    } 
    return retval 
} 

int anotherfunc(...) 
{ 
    uint8_t x = func(...) 

    /* binary and with 8 and shift 3 plaes to the right 
    * so that the resultant expression is either 1 or 0 */ 
    if (((x & 0x08) >> 3) == 1) 
    { 
     /* that error occurred */ 
    } 
} 

teraz do praktycznych. Gdy pamięć była rzadka, a protokoły nie miały luksusu pełnego xml itp., Często ograniczano pole jako tak wiele bitów. W tym polu przypisujesz różne bity (flagi, potęgi 2) do określonego znaczenia i stosujesz operacje binarne, aby wydedukować, czy są one ustawione, a następnie działają na nich.

Powinienem także dodać, że operacje binarne są bliskie idei dla podstawowej elektroniki komputera. Wyobraź sobie, że pola bitowe odpowiadają wyjściu różnych obwodów (prąd nośny lub nie). Używając wystarczającej liczby kombinacji tych obwodów, tworzysz ... komputer.

Answer 2

dotyczące wykorzystania tablicę bitów:

jeśli wiesz, że nie są „tylko” 1 milion numery - użyć tablicę 1 milion bitów. na początku wszystkie bity będą zerowe i za każdym razem, gdy przeczytasz cyfrę - użyj tej liczby jako indeksu i zmień bit w tym indeksie na jeden (jeśli już taki nie jest).

po odczytaniu wszystkich liczb - brakujące liczby są indeksami zer w tablicy.

na przykład, gdybyśmy mieli tylko liczby od 0 do 4, tablica wyglądałaby tak na początku: 0 0 0 0 0. jeśli odczytamy liczby: 3, 2, 2 tablica wyglądałaby jak to: przeczytaj 3 -> 0 0 0 1 0. czytaj 3 (ponownie) -> 0 0 0 1 0. czytaj 2 -> 0 0 1 1 0. sprawdź indeksy zer: 0,1,4 - to brakujące numery

BTW, oczywiście można użyć liczb całkowitych zamiast bitów, ale może to potrwać (zależnie od systemu) 32 razy pamięci

Sivan

Answer 3

który jest używany do przechowywanie znaczników bitów, a także parsowanie różnych pól protokołów binarnych, w których 1 bajt jest podzielony na kilka pól bitowych. Jest to powszechnie stosowane w protokołach takich jak TCP/IP, aż do kodowania ASN.1, pakietów OpenPGP i tak dalej.

Answer 4

Arytmy bitów wektoryzacji bitów są używane jako odwzorowanie od pozycji do pewnej wartości bitowej. Tak, to w zasadzie to samo, co tablica Bool, ale typowa implementacja Bool ma od jednego do czterech bajtów i zajmuje zbyt dużo miejsca.

Możemy przechowywać tę samą ilość danych o wiele bardziej wydajnie, używając tablic słów i operacji binarnego maskowania oraz przesuwania w celu ich przechowywania i pobierania (mniej ogólnej pamięci, mniej dostępu do pamięci, mniej pamięci podręcznej, mniej pamięci wymiany stronicowania). Kod dostępu do poszczególnych bitów jest nadal dość prosty.

Istnieje również wsparcie dla bitowych pól wbudowane w języku C (piszesz takie rzeczy jak int i:1;, aby powiedzieć "zużywaj tylko jeden bit"), ale nie jest on dostępny dla tablic i masz mniej kontroli nad ogólnym wynikiem (szczegóły implementacja zależy od problemów kompilatora i wyrównania).

Poniżej znajduje się możliwy sposób odpowiedzi na pytanie "szukaj brakujących numerów". Naprawiłem rozmiar int na 32 bity, aby zachować prostotę, ale można go zapisać za pomocą sizeof (int), aby był przenośny. I (w zależności od kompilatora i docelowego procesora) kod mógł być wykonany szybciej tylko za pomocą >> 5 zamiast / 32 i & 31 zamiast % 32, ale to tylko po to, aby dać pomysł.

#include <stdio.h> 
#include <errno.h> 
#include <stdint.h> 

int main(){ 
    /* put all numbers from 1 to 1000000 in a file, except 765 and 777777 */ 
    { 
     printf("writing test file\n"); 
     int x = 0; 
     FILE * f = fopen("testfile.txt", "w"); 
     for (x=0; x < 1000000; ++x){ 
      if (x == 765 || x == 777760 || x == 777791){ 
       continue; 
      } 
      fprintf(f, "%d\n", x); 
     } 
     fprintf(f, "%d\n", 57768); /* this one is a duplicate */ 
     fclose(f); 
    } 

    uint32_t bitarray[1000000/32]; 

    /* read file containing integers in the range [1,1000000] */ 
    /* any non number is considered as separator */ 
    /* the goal is to find missing numbers */ 
    printf("Reading test file\n"); 
    { 
     unsigned int x = 0; 
     FILE * f = fopen("testfile.txt", "r"); 
     while (1 == fscanf(f, " %u",&x)){ 
      bitarray[x/32] |= 1 << (x % 32); 
     } 
     fclose(f); 
    } 
    /* find missing number in bitarray */ 
    { 
     int x = 0; 
     for (x=0; x < (1000000/32) ; ++x){ 
      int n = bitarray[x]; 
      if (n != (uint32_t)-1){ 
       printf("Missing number(s) between %d and %d [%x]\n", 
        x * 32, (x+1) * 32, bitarray[x]); 
       int b; 
       for (b = 0 ; b < 32 ; ++b){ 
        if (0 == (n & (1 << b))){ 
         printf("missing number is %d\n", x*32+b); 
        } 
       } 
      } 
     } 
    } 
} 

Answer 5

Tablice bitowe lub wektory bitowe mogą być jednak tablicami wartości logicznych. Zwykle zmienna boolean wymaga co najmniej jednego bajtu, ale w bitowej tablicy/wektorze potrzebny jest tylko jeden bit. Jest to przydatne, jeśli masz dużo takich danych, dzięki czemu można zaoszczędzić całą pamięć.

Innym zastosowaniem jest, jeśli masz numery , które nie pasują dokładnie do standardowych zmiennych o rozmiarze 8,16,32 lub 64-bitowym. W ten sposób można zapisać w wektorze bitowym 16-bitowym liczbę składającą się z 4-bitów, jedną 2-bitową i jedną 10-bitową. Normalnie będziesz musiał użyć 3 zmiennych o rozmiarach 8,8 i 16 bitów, więc masz tylko 50% zmarnowanego miejsca.

Ale wszystkie te zastosowania są bardzo rzadko stosowane w Aplikacje biznesowych, pochodzą często używany podczas łączenia sterowników poprzez pinvoke/współdziałanie funkcje i sposób programowania niski poziom.