Operacje bitowe w algorytmach

Wprowadzenie

Operacje bitowe to fundamentalne operacje wykonywane bezpośrednio na pojedynczych bitach liczb w ich reprezentacji binarnej. Są one wyjątkowo szybkie (wykonywane w 1 cyklu procesora) i stanowią podstawę wielu zaawansowanych algorytmów i optymalizacji.

Operacje bitowe są kluczowe w:

Optymalizacji algorytmów (mnożenie/dzielenie przez potęgi 2)
Manipulacji flagami (uprawnienia, stany)
Grafice komputerowej (manipulacja kolorami, pikselami)
Kryptografii (szyfrowanie, hashe)
Kompresji danych (kodowanie, dekodowanie)
Systemach embedded (kontrola rejestrów, I/O)
Strukturach danych (Bloom filters, bitmaps)

Podstawowe operacje bitowe

1. AND (koniunkcja bitowa) - `&`

Zasada: Wynik = 1 tylko gdy oba bity = 1

Tablica prawdy:
  0 & 0 = 0
  0 & 1 = 0
  1 & 0 = 0
  1 & 1 = 1

Przykład:

  1010 (10)
& 1100 (12)
------
  1000 (8)

Implementacja:

Wyjście:

=== Operacja AND (&) ===

   0b1010 (10)
&  0b1100 (12)
---------------
   0b1000 (8)

2. OR (alternatywa bitowa) - `|`

Zasada: Wynik = 1 gdy przynajmniej jeden bit = 1

Tablica prawdy:
  0 | 0 = 0
  0 | 1 = 1
  1 | 0 = 1
  1 | 1 = 1

Przykład:

  1010 (10)
| 1100 (12)
------
  1110 (14)

Implementacja:

Wyjście:

=== Operacja OR (|) ===

   0b1010 (10)
|  0b1100 (12)
---------------
   0b1110 (14)

3. XOR (różnica symetryczna) - `^`

Zasada: Wynik = 1 gdy bity są różne

Tablica prawdy:
  0 ^ 0 = 0
  0 ^ 1 = 1
  1 ^ 0 = 1
  1 ^ 1 = 0

Przykład:

  1010 (10)
^ 1100 (12)
------
  0110 (6)

Implementacja:

Wyjście:

=== Operacja XOR (^) ===

   0b1010 (10)
^  0b1100 (12)
---------------
   0b0110 (6)

4. NOT (negacja bitowa) - `~`

Zasada: Odwraca wszystkie bity (0→1, 1→0)

Tablica prawdy:
  ~0 = 1
  ~1 = 0

Uwaga: W Pythonie ~x zwraca -(x+1) (ze względu na reprezentację liczb ze znakiem)

Przykład:

~1010 = ...11110101  (uzupełnienie do dwóch)

W Pythonie:
~10 = -11

Implementacja:

Wyjście:

=== Operacja NOT (~) ===

Liczba:        10 = 0b1010
NOT:          -11 = 0b11111111111111111111111111110101

Uwaga: ~10 = -11 = -11 (kod uzupełnień do dwóch)

Przesunięcia bitowe

1. Przesunięcie w lewo - `<<`

Zasada: Przesuń wszystkie bity w lewo, dodaj zera z prawej

x << n  =  x * 2^n

Przykład:

5 << 1:  0101 → 1010  (5 * 2 = 10)
5 << 2:  0101 → 10100 (5 * 4 = 20)

Implementacja:

Wyjście:

=== Przesunięcie w lewo (<<) ===

Operacja     Binarnie        Dziesiętnie
---------------------------------------------
x = 5        0b101           5
x << 1       0b1010          10 (= 5 × 2^1)
x << 2       0b10100         20 (= 5 × 2^2)
x << 3       0b101000        40 (= 5 × 2^3)

2. Przesunięcie w prawo - `>>`

Zasada: Przesuń wszystkie bity w prawo, usuń bity z prawej

x >> n  =  x // 2^n  (dzielenie całkowite)

Przykład:

20 >> 1:  10100 → 1010  (20 // 2 = 10)
20 >> 2:  10100 → 101   (20 // 4 = 5)

Implementacja:

Wyjście:

=== Przesunięcie w prawo (>>) ===

Operacja     Binarnie        Dziesiętnie
---------------------------------------------
x = 20       0b10100         20
x >> 1       0b1010          10 (= 20 // 2^1)
x >> 2       0b101           5 (= 20 // 2^2)
x >> 3       0b10            2 (= 20 // 2^3)

Praktyczne zastosowania

1. Sprawdzanie i ustawianie bitów

Wyjście:

=== Manipulacja bitami ===

Liczba początkowa: 0b1010 (10)

Bit na pozycji 0: 0
Bit na pozycji 1: 1
Bit na pozycji 2: 0
Bit na pozycji 3: 1

Po ustawieniu bitu 0:   0b1011 (11)
Po wyzerowaniu bitu 3:  0b10 (2)
Po przełączeniu bitu 2: 0b1110 (14)

2. Liczenie bitów = 1 (Population Count)

Wyjście:

=== Liczenie bitów = 1 ===

Liczba     Binarnie        Bity = 1
----------------------------------------
0          0b0             0
7          0b111           3
15         0b1111          4
255        0b11111111      8
170        0b10101010      4
1023       0b1111111111    10

3. Sprawdzanie potęgi dwójki

Wyjście:

=== Sprawdzanie potęgi dwójki ===

Liczba     Binarnie        Potęga 2?
----------------------------------------
0          0b0             ✗ NIE
1          0b1             ✓ TAK
2          0b10            ✓ TAK
3          0b11            ✗ NIE
4          0b100           ✓ TAK
5          0b101           ✗ NIE
8          0b1000          ✓ TAK
15         0b1111          ✗ NIE
16         0b10000         ✓ TAK
32         0b100000        ✓ TAK
100        0b1100100       ✗ NIE
128        0b10000000      ✓ TAK

4. Maski bitowe i flagi

Wyjście:

=== Flagi bitowe (uprawnienia) ===

Start:          Permissions(READ, WRITE) [0b11]
Po grant(EXEC): Permissions(READ, WRITE, EXECUTE) [0b111]
Po revoke(WR):  Permissions(READ, EXECUTE) [0b101]

Sprawdzenia:
  Czy ma READ?    True
  Czy ma WRITE?   False
  Czy ma EXECUTE? True

5. Zamiana dwóch liczb bez zmiennej tymczasowej

Wyjście:

=== Zamiana wartości przez XOR ===

Start: a = 10, b = 20
Po a = a ^ b:  a = 30, b = 20
Po b = a ^ b:  a = 30, b = 10
Po a = a ^ b:  a = 20, b = 10

6. Znajdowanie najmłodszego bitu = 1

Wyjście:

=== Najmłodszy bit = 1 ===

Liczba          Binarnie        Pozycja LSB
---------------------------------------------
10              0b1010          1
12              0b1100          2
8               0b1000          3
31              0b11111         0
128             0b10000000      7

Zaawansowane techniki

1. Izolowanie bitów w zakresie

Wyjście:

=== Wyodrębnianie bitów ===

Liczba: 0b11010110 (214)

Najmłodsze 4 bity          →     0b110 (6)
Bity 4-7                   →    0b1101 (13)
Bity 2-4                   →     0b101 (5)

2. Odwracanie bitów

Wyjście:

=== Odwracanie bitów ===

Oryginał        Odwrócone
------------------------------
0b1             0b10000000
0b10101010      0b1010101
0b11110000      0b1111
0b1111          0b11110000

3. Parzystość (Parity)

Wyjście:

=== Parzystość bitowa ===

Liczba          Binarnie        Bity=1     Parzystość
-------------------------------------------------------
0               0b0             0          PARZYSTA
1               0b1             1          NIEPARZYSTA
3               0b11            2          PARZYSTA
7               0b111           3          NIEPARZYSTA
15              0b1111          4          PARZYSTA
21              0b10101         3          NIEPARZYSTA
255             0b11111111      8          PARZYSTA

Optymalizacje algorytmiczne

1. Szybkie mnożenie/dzielenie przez potęgi 2

Wyjście:

=== Szybkie mnożenie/dzielenie ===

Liczba: 42

Mnożenie:
  42 × 2^1 = 42 << 1 = 84 (sprawdzenie: 84)
  42 × 2^2 = 42 << 2 = 168 (sprawdzenie: 168)
  42 × 2^3 = 42 << 3 = 336 (sprawdzenie: 336)
  42 × 2^4 = 42 << 4 = 672 (sprawdzenie: 672)

Dzielenie:
  42 // 2^1 = 42 >> 1 = 21 (sprawdzenie: 21)
  42 // 2^2 = 42 >> 2 = 10 (sprawdzenie: 10)
  42 // 2^3 = 42 >> 3 = 5 (sprawdzenie: 5)

2. Sprawdzanie parzystości/nieparzystości

Wyjście:

=== Parzystość/nieparzystość ===

Liczba     Binarnie        Parzysta?    Nieparzysta?
-------------------------------------------------------
0          0b0             True         False
1          0b1             False        True
2          0b10            True         False
3          0b11            False        True
10         0b1010          True         False
15         0b1111          False        True
42         0b101010        True         False
99         0b1100011       False        True
100        0b1100100       True         False

Podsumowanie

Podstawowe operacje

Operacja	Symbol	Opis	Przykład
AND	`&`	Koniunkcja (oba = 1)	`1010 & 1100 = 1000`
OR	`\\|`	Alternatywa (któryś = 1)	`1010 \\| 1100 = 1110`
XOR	`^`	Różnica (różne)	`1010 ^ 1100 = 0110`
NOT	`~`	Negacja (odwrócenie)	`~1010 = ...0101`
Shift L	`<<`	Przesunięcie w lewo	`5 << 2 = 20`
Shift R	`>>`	Przesunięcie w prawo	`20 >> 2 = 5`

Przydatne triki

✅ Sprawdzenie bitu:        n & (1 << k)
✅ Ustawienie bitu:         n | (1 << k)
✅ Wyzerowanie bitu:        n & ~(1 << k)
✅ Przełączenie bitu:       n ^ (1 << k)
✅ Sprawdzenie potęgi 2:    n & (n-1) == 0
✅ Najmłodszy bit = 1:      n & (-n)
✅ Parzystość:              n & 1 == 0
✅ Mnożenie przez 2^k:      n << k
✅ Dzielenie przez 2^k:     n >> k

Zastosowania

✅ Optymalizacje: szybkie mnożenie/dzielenie ✅ Flagi: uprawnienia, stany, konfiguracje ✅ Grafika: manipulacja kolorami, pikselami ✅ Kryptografia: operacje na blokach danych ✅ Kompresja: kodowanie, dekodowanie ✅ Struktury danych: Bloom filters, bitmaps

Co dalej?

Po opanowaniu operacji bitowych, następne kroki to:

Lekcja 65: Liczby pierwsze - test pierwszości
Algorytmy sprawdzania pierwszości
Optymalizacje
Lekcja 66: Sito Eratostenesa
Generowanie liczb pierwszych
Implementacje
Lekcja 67: Algorytm Euklidesa - NWD
Największy wspólny dzielnik
Zastosowania

Zadania praktyczne

Zadanie 1: Kompresja bitmap

Zaimplementuj prostą kompresję czarno-białych obrazów używając operacji bitowych (1 bit = 1 piksel).

Zadanie 2: System uprawnień rozszerzony

Stwórz system uprawnień z hierarchią (np. ADMIN ma wszystkie uprawnienia automatycznie) używając flag bitowych.

Zadanie 3: Checksum/CRC

Zaimplementuj prosty algorytm obliczania sumy kontrolnej używając XOR.

Zadanie 4: Bit twiddling challenges

Rozwiąż klasyczne zadania: - Policz liczbę bitów różniących się między dwiema liczbami - Znajdź najbliższą większą liczbę z tą samą liczbą bitów = 1 - Sprawdź czy liczba jest palindromem binarnym

Następna lekcja: Liczby pierwsze - test pierwszości

Operacje bitowe w algorytmach

Wprowadzenie

Podstawowe operacje bitowe

1. AND (koniunkcja bitowa) - &

2. OR (alternatywa bitowa) - |

3. XOR (różnica symetryczna) - ^

4. NOT (negacja bitowa) - ~

Przesunięcia bitowe

1. Przesunięcie w lewo - <<

2. Przesunięcie w prawo - >>

Praktyczne zastosowania

1. Sprawdzanie i ustawianie bitów

2. Liczenie bitów = 1 (Population Count)

3. Sprawdzanie potęgi dwójki

4. Maski bitowe i flagi

5. Zamiana dwóch liczb bez zmiennej tymczasowej

6. Znajdowanie najmłodszego bitu = 1

Zaawansowane techniki

1. Izolowanie bitów w zakresie

2. Odwracanie bitów

3. Parzystość (Parity)

Optymalizacje algorytmiczne

1. Szybkie mnożenie/dzielenie przez potęgi 2

2. Sprawdzanie parzystości/nieparzystości

Podsumowanie

Podstawowe operacje

Przydatne triki

Zastosowania

Co dalej?

Zadania praktyczne

Zadanie 1: Kompresja bitmap

Zadanie 2: System uprawnień rozszerzony

Zadanie 3: Checksum/CRC

Zadanie 4: Bit twiddling challenges

1. AND (koniunkcja bitowa) - `&`

2. OR (alternatywa bitowa) - `|`

3. XOR (różnica symetryczna) - `^`

4. NOT (negacja bitowa) - `~`

1. Przesunięcie w lewo - `<<`

2. Przesunięcie w prawo - `>>`