Następny zalążek historii programowania. Opowiem dzisiaj o tym, jak w latach .80 trzeba było często stosować inny zapis do wykonywania działań arytmetycznych na liczbach całkowitych (i nic nie stoi na przeszkodzie, aby dzisiaj z tego korzystać ;)). Kolejny temat i kolejny termin: "przesunięcie bitowe".
| Tweet |
PRZESUNIĘCIE BITOWE. KAWAŁEK HISTORII
Cofamy się do czasów gdy ludzie musieli jeszcze sobie radzić z pisaniem programów jedynie przy pomocy asemblera. Ówczesne procesory były daleko odbiegające od dzisiejszych. Bardzo łatwo można było przesadzić z przekroczeniem maksymalnej wydajności i sprawić, żeby wszystko zakończyło się fiaskiem. Nawet proste operacje arytmetyczne wymagały starannej analizy. W latach .80 nie można było regularnie tak sobie pisać "razy trzy" czy "podzielić przez osiem". Trzeba było korzystać z wydajniejszej formy zapisu. Mniej zrozumiała dla człowieka, ale dużo przyjaźniejsza dla komputera.
W tamtych czasach taki trik nazywał się "przesunięcie bitowe". Polegał on na "przesuwaniu" wszystkich bitów w ciągu binarnym w lewo (jeśli mnożenie) lub w prawo (jeśli dzielenie). Ciężko mi dzisiaj ocenić czy ma to jakiś znaczny wpływ na dzisiejsze procesory i kompilatory (możliwe, że one same już dokonują takich optymalizacji). Wiem tylko, że kiedyś miało to kolosalne znaczenie bo to był mniejszy wysiłek dla komputera. Dlaczego?
Przy zwykłym mnożeniu przez dwa, obie liczby binarne musiały zostać dodane do siebie w związku z czym, wiązały się operacje kalkulacji oczekiwanego wyniku. Natomiast gdy zastosowało się przesunięcie bitowe, liczba binarna musiała jedynie mieć przestawione bity i na tym kończyła się operacja. Za dużo teorii o działaniu CPU, żebym się tu rozpisywał. Tu macie mocno "ściśnięte" porównanie obu wariantów.
SPOSÓB DZIAŁANIA PRZESUNIĘĆ
Banalny szacher macher. Mamy taką oto liczbę w systemie binarnym:
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
W systemie dziesiętnym to jest 106. Załóżmy, że chcemy ją przemnożyć przez dwa. Stosując przesunięcie bitowe w lewo o 1, mnożymy wówczas przez dwa!
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
106*2 wynosi 212. Sprawdźcie sami czy przypadkiem nie wyszło tak samo w reprezentacji bitowej powyżej.
A teraz dzielenie. Iloczyn wychodzi prosto, natomiast jeśli przychodzi przypadek dzielenia z resztą, wtedy ułamek jest "obcinany", nie zaokrąglany! Rozpatrzmy taki przypadek:
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
To jest liczba 69. Przesunięcie bitowe o jedno miejsce w prawo (czyli dzielenie przez dwa) daje z kolei taki wynik. Dwa razy zastanówcie się nad odpowiedzią:
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
Zauważyliście to? Nie 34,5, tylko samo 34! Ten, kto ćwiczył konwersję na system binarny, nie powinien być zaskoczony. To były proste przykłady, natomiast można przesuwać o więcej miejsc. Aby to robić świadomie, trzeba wiedzieć w jaki sposób to działa. Sięgajcie okiem poniżej.
JAK WYKORZYSTAĆ PRZESUNIĘCIE BITOWE W KODZIE?
Tyle teorii wystarczy, abyście nie czuli się zakłopotani. Tak wygląda zapis przesunięcia bitowego w języku C:
[liczba całkowita] << N
[liczba całkowita] >> N
Choć manewr ten może się dzisiaj wydawać bezużyteczny, to mimo wszystko warto wiedzieć w jaki inny sposób można dokonywać operacji. No właśnie, ale jakich operacji? Jedynie mnożenie i dzielenie (strzałki skierowane w lewo i w prawo). I nie przez dowolny czynnik tylko przez potęgę liczby 2. To znaczy, że jak chcę podzielić liczbę przez dwa, to piszę tak:
[liczba całkowita] >> 1
Za N, podstawiacie potęgę liczby 2, czyli dla dwójki to będzie dzielenie przez cztery, dla trójki, dzielenie przez osiem i tak dalej, i tak dalej. To nie jest nic trudnego, wystarczy znać przebieg działania. Jeśli do teraz wydaje się Wam to bezsensowne, z biegiem czasu zmienicie myślenie.
No i pamiętajcie, że to Wam wolno wstawić w stosunku do wyłącznie liczb całkowitych i zmiennych całkowitoliczbowych!
To tyle z mojej strony na temat przesunięć bitowych. Kiedyś miało to ogromne znaczenie, a teraz jest to traktowane jak element historii, choć może stanowić miły dla oka pokaz Waszego profesjonalizmu ;).