Strona główna » Algorytmy » Artykuły » Liczba Różnych Bitów
 

Liczba Różnych Bitów

https://mattomatti.com/a0033

Wstęp

Wszystkie dane są przechowywane w komputerze w postaci ciągu bitów. Dzięki porównaniu różnicy ich bitów można łatwo stwierdzić czy dane są identyczne, albo czym się różnią. Najwygodniejszym sposobem wybierania i porównywania bitów jest zastosowanie operacji binarnych. Opis wybranych operacji logicznych można znaleźć artykule o matrycach logicznych.

Przedstawione w artykule zadanie polega na wyznaczeniu ilości różnych bitów między dwoma liczbami całkowitymi.

Implementacja

Wybieranie bitu

Jednym z najprostszych sposobów dzieki którem można zrealizować zadanie jest wybieranie kolejnych bitów z liczby. W tym celu użyjemy operacji AND.

  1. int ileRoznychBitow(int a, int b) {
  2.   int ileRoznych = 0;
  3.   for (int wybierz = 1; wybierz != 0; wybierz <<= 1) {
  4.     if ((a & wybierz) != (b & wybierz)) {
  5.       ileRoznych++;
  6.     }
  7.   }
  8.   return ileRoznych;
  9. }

(1.) Funkcja przyjmuje dwie liczby całkowite i (2.) deklaruje licznik, który będzie zliczał ile jest różnych bitów. W dalszej częśći (3.) deklarowana jest pętla, która będzie przechodzić po kolejnych bitach liczb. (4.) Jeśli wybrane bity są różne to (5.) należy zwiększyć licznik. Na koniec (8.) pozostaje zwrócić wynik liczby.

XOR

Poprzednie rozwiązanie jest bardzo proste i intuicyjne. Jednak do tego zadania można zastosować również operację XOR. Jest to operacja, która ma następującą matrycę logiczną:

pqp XOR q
000
101
011
110

Jak można zauważyć tylko dla różnych wartości zostanie zwrócona prawda, a w pozostałych przypadkach fałsz. Oznacza to, że można zamiast operatora nierówna się zastosować XOR, albo zastosować tę operację na obydwu liczbach równocześnie i policzyć ilość bitów 1 w rezultacie tej operacji.

Rozwiązanie drugim sposobem realizuje poniższy algorytm:

  1. int ileRoznychBitow(int a, int b) {
  2.   int w = a ^ b;
  3.   int ileRoznych = 0;
  4.   for (int wybierz = 1; wybierz != 0; wybierz <<= 1) {
  5.     if (w & wybierz) {
  6.       ileRoznych++;
  7.     }
  8.   }
  9.   return ileRoznych;
  10. }

(2.) Wykonaj operację XOR, a potem (3.) zadeklaruj licznik. (4. - 8.) Tym razem wystarczy wybierać bity tylko z jednej liczby. Można tego dokonać przy pomocy podobnej pętli co w poprzednim przykładzie.

Testowanie funkcji

W celu przetestowanie funkcji można zastosować poniższą funkcję main():

  1. int main () {
  2.   int a, b;
  3.   cout << "Podaj liczby\na = ";
  4.   cin >> a;
  5.   cout << "b = ";
  6.   cin >> b;
  7.   cout << "Liczby " << a << " i " << b << " maja ";
  8.   cout << ileRoznychBitow(a, b) << " roznych bitow\n";
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Napisz algorytm, który sprawdzi ile jest identycznych bitów, a potem na podstawie tej wartości wyliczy ile jest różnych bitów. Zmień również sposób obliczania wartości zmiennej wybierz. Pamiętaj, że w zależności od typu zmiennej liczba bitów może się różnić!