Reprezentacja liczb
Ta lekcja skupia się na operacjach
bitowych na liczbach całkowitych. Pozwalają one modyfikować liczby przez modyfikację ich reprezentacji. Do tej pory zapis liczb w komputerze nie był w tym kursie omawiany, bo nie było to potrzebne do rozumienia operacji na zmiennych i posługiwania się nimi. Jedyną wskazówką co do działania zmiennych były ich zakresy wartości, których granice nie są zbyt okrągłymi wartościami - a przynajmniej nie w systemie
dziesiętnym. Rozumienie sposobu reprezentacji liczb całkowitych jest za to
niezbędne do zrozumienia operacji bitowych, które, jak nazwa wskazuje, operują na bitach liczby. To zasadniczo podstawowa wiedza informatyczna, ale dla kompletności wypada to omówić.
Komputer jest skomplikowanym cyfrowym układem elektronicznym. Wobec tego podstawową,
niepodzielną jednostką informacji jest
bit, który przyjmuje wartości 1 lub 0. Albo, jak to się częściej oznacza w tematyce elektroniki cyfrowej, H i L, oznaczające stan wysoki napięcia oraz niski.
Pojedyncze bity są mało przydatne, dlatego łączy się je
słowa, tak samo jak pojedyncze litery są mało przydatne i łączy się je w, cóż, słowa. Słowo mające N bitów ma 2
N możliwych kombinacji bitów. Te kombinacje można różnie ponumerować, patrz: kod Grey'a, lub naturalny kod binarny. My będziemy zajmować się tym drugim. W naturalnym kodzie binarnym n-ta kombinacja bitów to liczba n zapisana w systemie dwójkowym, dopełniona nieznaczącymi zerami do N bitów pojemności słowa. System dwójkowy to taki sam liczbowy system pozycyjny, jak system dziesiętny. Tylko że o podstawie 2, a nie 10. Mam nadzieję, że to nie sprawia problemów, bo to nie jedyny nowy system liczbowy jaki będzie tu omówiony.
| A jeśli sprawia problemy, to Windowsowy kalkulator (od Windows 7 w górę) ma "tryb Programisty", który pozwala konwertować i operować na liczbach w systemach dwójkowym, ósemkowym, dziesiętnym i szesnastkowym. |
Kolejną fundamentalną jednostką danych jest
bajt, który składa się z 8 bitów i jest najmniejszą
adresowalną jednostką informacji. Nie można się odwołać do konkrentego bitu w pamięci inaczej niż przez odwołanie się do bajtu, który ten bit zawiera, i wyciągnięcie wartości bitu z pomocą operacji bitowych.
Warto wiedzieć, że bajt jest adresowalny dla programu i w pamięci operacyjnej. W rzeczywistości różne urządzenia, jak dysk twardy, czy nawet sama pamięć RAM (!) może używać większych jednostek danych jako swoich najmniejszych adresowalnych. Z dysku twardego nie da się naraz wyciągnąć mniej niż cały sektor, który ma w starszych urządzeniach 512 bajtów, a w nowszych 4096 bajtów. Gdy długość adresu jest ograniczona, ograniczona jest też maksymalna adresowalna pojemność. Stąd systemy 32-bitowe nie obsługują więcej niż 4GB pamięci RAM.
Przez to że zmienne w pamięci chcemy adresować i nie chcemy przy tym marnować bitów, rozmiary zmiennych to wielokrotności 8 bitów.
Liczby ujemne
Naturalnego kodu binarnego możemy się spodziewać w zmiennych bez znaku
unsigned, jednak co ze zmiennymi ze znakiem? Trzeba jakoś wyrazić minus przed liczbą ujemną, a mają do dyspozycji wyłącznie N bitów szybko okazuje się, że trzeba użyć innego kodu do zapisywania takich liczb. Opcji jest kilka:
Słówko wyjaśnienia:
najstarszy bit oznacza bit o najwyższej wadze w słowie (ang. MSB,
most significant bit). Przeciwieństem jest
bit najmłodszy (ang. LSB,
least significant bit), który ma wagę równą 1.
Standard C++ nie narzuca wymagań na reprezentację liczb, ale jak się zapewne domyślasz, jest to kwestia sprzętowa, a nie języka programowania. Najpopularniejszym kodem do zapisu liczb ze znakiem jest kod U2. Oto wszystkie liczby 4-bitowe w omówionych kodowaniach:
Warto znać kilka skrajnych przypadków w kodzie U2. Ale zamiast je wbić jak tabliczkę mnożenia, prościej je rozumieć. W matematyce, w sysemie pozycyjnym cyfra na danej pozycji ma wagę o 1 większą niż wartość osiągalna na wszystkich młodszych pozycjach razem wziętych (na przykład 1000 i 999 dziesiętnie). To samo w systemie binarnym (1000
2 i 111
2). W kodzie U2 najstarszy bit ma ujemną wagę, więc najmniejsza wartość, to 1 na najstarszym bicie i zera wszędzie indziej (1000..0). Przez to że młodsze bity mogą osiągnąć wartość mniejszą o 1 od największej wagi, liczba -1 jest reprezentowana samymi jedynkami (1111..1). I oczywiście, najmniejsza i największa wartość dodatnia jest reprezentowana jak w naturalnym kodzie binarnym, z doklejonym najstarszym zerem (0000..0 i 0111..1). Taki system jest
asymetryczny, jest tylko jedna reprezentacja zera, ale za to liczb ujemnych jest więcej niż dodatnich. Stąd zakres liczb ze znakiem o długości N bitów to [-2
N-1; 2
N-1-1], co wyjaśnia liczby w zakresach wartości typów podane na początku kursu.
| Są jeszcze typy zmiennoprzecinkowe float, double i long double, które mają podane niebotyczne zakresy przy podejrzanie małej liczbie bajtów. Sztuczka w tym, że nie wszystkie liczby w tym ogromnym przedziale są reprezentowalne. Im dalej od zera, tym mniejsza precyzja. W efekcie reprezentacja i operacje na takich liczbach stają się nietrywialne. Operacje bitowe nie działają na liczbach zmiennoprzecinkowych. Tu najpopularniesze zagospodarowanie bitów opisuje standard IEEE 754. |
Negacja bitowa
Pora przejść do omawiania operacji bitowych dostępnych w C++. Najprostszym operatorem jest
negacja bitowa, która neguje wszystkie bity w podanej liczbie. Jej operatorem jest tylda (
~) i jest operatorem jednoargumentowym, tak jak negacja logiczna.
#include <iostream>
int main()
{
unsigned char test = 42;
std::cout << "Negacja bitowa: " << ~test << '\n';
std::cout << "Negacja logiczna: " << !test << '\n';
}
Negacja bitowa: -43
Negacja logiczna: 0
Zwróć uwagę, że wynik negacji bitowej jest ujemny i o 1 mniejszy od wartości źródłowej. W kodzie U2 zmianę znaku można uzyskać przez zanegowanie wszystkich bitów i dodanie jedynki. Na przykładzie zera, zanegowanie bitów daje same jedynki czyli -1 i przez dodanie jedynki wracamy do samych zer i wartości 0. W końcu, U2 ma tylko jedno zero.
A, no i odwracam uwage od faktu że wynik jest ujemny. Przecież wartość źródłowa to
unsigned char, dlaczego wynik jest ze znakiem? To dlatego, że użyliśmy małego typu. Typy mniejsze od
int podlegają niejawnej konwersji do
int. Taka konwersja nazywa się promocją całkowitoliczbową. Aby wynik był bardziej pasujący do naszych intencji, trzeba rzutować do interesującego nas typu. Żeby nie zaciemniać przykładu, użyjemy rzutowania w stylu C:
std::cout << "Negacja bitowa: " <<( int )( unsigned char ) ~test << '\n';
Negacja bitowa: 213
To wymaga komentarza. Samo rzutowanie do
unsigned char sprawi, że wynik zostanie wypisany jako jeden znak o zadanym kodzie, dlatego trzeba dodatkowo rzutować na
int, by została wypisana liczba. A co się stanie, jeśli spróbujemy pójść na skróty i rzutujemy do
unsigned int?
std::cout << "Negacja bitowa: " <<( unsigned int ) ~test << '\n';
Negacja bitowa: 4294967253
Kod U2 ma taką własność: jeśli chcemy wydłużyć liczbę, to należy powielać najstarszy bit. W liczbie ujemnej jest to 1, więc zamiast wypisać liczbę bez znaku "00000..", wypisaliśmy "11111..", a więc znacznie większą niż chcieliśmy.
Operacje na dwóch liczbach
Teraz zajmiemy się bardziej przydatnymi rzeczami, operacjami które łączą ze sobą bity z dwóch liczb by wygenerować wynik. W C++ są operatory
alternatywy bitowej | i
koniunkcji bitowej & - zwróć uwagę, że to te same znaki co w przypadku alternatywy i koniunkcji logicznej, tylko że występujące pojedynczo, a nie w parze. Dodatkowo mamy do dyspozycji operator
alternatywy wykluczającej, inaczej
sumy modulo 2, albo
XOR (ang.
exclusive or), zapisywany znakiem daszka
^.
Operacje te biorą jeden bit z obu liczb i wynikiem jest jeden bit liczby wynikowej. I tak dalej do zużycia wszystkich bitów wejściowych i wyznaczenia wszystkich bitów wyjściowych. Przez to że operacja działa na dwóch bitach naraz, są 4 możliwe przypadki dla każdej pary bitów. Przedstawia je tabela:
AND i OR działają tak jak ich logiczne odpowiedniki. XOR daje w wyniku 1, tylko wtedy, jeśli bity się
różnią, więc można powiedzieć że jest to negacja równoważności. Można też powiedzieć, że to suma dwóch bitów wejściowych, przycięta do jednego bitu. 1 + 1 = 10
2, po przycięciu zostaje zero, stąd jest to suma modulo 2.
#include <iostream>
void printBits( unsigned int n )
{
const int Bits = 8 * sizeof n;
char tmp[ Bits + 1 ];
for( int i = 0; i < Bits; ++i )
{
tmp[ Bits - i - 1 ] = '0' + n % 2;
n /= 2;
}
tmp[ Bits ] = 0;
std::cout << tmp;
}
void showOperation( unsigned int a, unsigned int b, unsigned int result, char op )
{
std::cout << " ";
printBits( a );
std::cout << " (" << a << ")\n " << op << ' ';
printBits( b );
std::cout << " (" << b << ")\n = ";
printBits( result );
std::cout << " (" << result << ")\n\n";
}
int main()
{
unsigned int a = 42, b = 57;
showOperation( a, b, a | b, '|' );
showOperation( a, b, a & b, '&' );
showOperation( a, b, a ^ b, '^' );
}
00000000000000000000000000101010 (42)
| 00000000000000000000000000111001 (57)
= 00000000000000000000000000111011 (59)
00000000000000000000000000101010 (42)
& 00000000000000000000000000111001 (57)
= 00000000000000000000000000101000 (40)
00000000000000000000000000101010 (42)
^ 00000000000000000000000000111001 (57)
= 00000000000000000000000000010011 (19)
| Operatory |, & i ^ mają niższe priorytety od <<, więc pamiętaj o nawiasach przy podawaniu wyrażenia z nimi prosto do std::cout. |
Więcej o XOR
Operacja XOR jest łączna i przemienna. XORowanie bitu przez 0 nie zmienia go, a przez 1 neguje go. Można więc myśleć o XOR jak o "wybiórczej negacji bitowej", można zanegować wybrane bity w liczbie sporządzajac odpowiednią maskę bitową i stosując operację XOR. Z tej "wybiórczej negacji" (albo z "negacji równoważności") możemy wydedukować kolejne właściwości: dla dowolnego A, A XOR A jest równe 0. (XORowanie liczby samej przez siebie jest często spotykane w kodzie maszynowym do zerowania rejestrów.) Jest to operacja
odwracalna: wybiórczo negujemy te same bity 2 razy i mamy to z czym zaczęliśmy. Każda zmiana jednego bitu na wejściu na przeciwny powoduje zmianę odpowiedniego bitu wyjścia na przeciwny. To sprawia, że ta operacja jest wprost nieoceniona w kryptografii. Na przykład szyfr AES używa operacji XOR do wprowadzania klucza rundy do bloków szyfru. Oprócz tego jest wykorzystywana w większości funkcji skrótu i sumach kontrolnych.
Te właściwości możemy wykorzystać do zamienienia miejscami dwóch liczb
in situ, tzn bez dodatkowych zmiennych:
#include <iostream>
int main()
{
unsigned int a = 42, b = 57;
std::cout << a << ' ' << b << '\n';
a ^= b;
b ^= a;
a ^= b;
std::cout << a << ' ' << b << '\n';
}
42 57
57 42
Przesunięcia bitowe
Ostatnie dwie operacje pozwalają na
przesuwanie bitów w lewo i prawo. Służa do tego operatory
<< i
>>. Przed operatorem podajemy liczbę, którą chcemy przesunąć, a po nim podajemy o ile bitów chcemy przesuwać. Przesuwanie bitów w lewo oznacza przesuwanie ich w stronę starszych bitów, a miejsca zwolnione po najmłodszych bitach są wypełniane zerami. W liczbie przesuniętej o N pozycji w lewo, bity zostają przesunięte na pozycje o wyższych wagach, więc jest to równoznaczne z
pomnożeniem razy 2N. Analogicznie, przesuwanie w prawo jest równoznaczne z dzieleniem liczby przez 2
N.
Te operatory nie są między sobą zamienne. Nie można przesuwać w prawo o -2, żeby przesunąć w lewo o 2. Po prawej stronie operatora przesunięcia musi stać liczba
nieujemna,
mniejsza od rozmiaru liczby po lewej stronie operatora (po ewentualnych promocjach całkowitoliczbowych).
int main()
{
unsigned int a = 42;
printBits( a );
std::cout << " (" << a << ")\n";
a <<= 4;
printBits( a );
std::cout << " (" << a << ")\n";
a >>= 7;
printBits( a );
std::cout << " (" << a << ")\n";
}
00000000000000000000000000101010 (42)
00000000000000000000001010100000 (672)
00000000000000000000000000000101 (5)
W przypadku liczb ujemnych, zachowanie przesunięć jest zależne od implementacji (w końcu nie jest narzucona reprezentacja liczb całkowitych). W szczególności, w przypadku kodu U2, przesunięcie w prawo nie będzie działać dokładnie tak jak dzielenie przez potęgę dwójki.
int main()
{
int a = - 42;
for( int i = 0; i < 10; ++i )
{
printBits( a );
std::cout << " (" << a << ")\n";
a >>= 1;
}
}
11111111111111111111111111010110 (-42)
11111111111111111111111111101011 (-21)
11111111111111111111111111110101 (-11)
11111111111111111111111111111010 (-6)
11111111111111111111111111111101 (-3)
11111111111111111111111111111110 (-2)
11111111111111111111111111111111 (-1)
11111111111111111111111111111111 (-1)
11111111111111111111111111111111 (-1)
11111111111111111111111111111111 (-1)
Przesunięcie w prawo nie sprowadzi -1 do 0 z powodu tych jedynek ciągniętych od bitu znaku. Dla liczb dodatnich będzie działać sposób równoważny z dzieleniem.
Przykład
W ramach przykładu, zaimplementujemy sobie dodawanie dwóch liczb używając tylko operacji bitowych.
#include <iostream>
int add( int a, int b )
{
if( b == 0 )
return a;
return add( a ^ b,( a & b ) << 1 );
}
int main()
{
int a, b;
std::cout << "Podaj dwie liczby:\n";
std::cin >> a >> b;
std::cout << a << " + " << b << " = " << add( a, b ) << '\n';
}
Podaj dwie liczby:
681 -365
681 + -365 = 316
XOR jest sumą modulo 2, więc jedyne czego mu brakuje do bycia pełną sumą, to uwzględnienie przeniesienia. Przeniesienie możemy wyznaczyć koniunkcją bitową, a potem wystarczy je dodać do wyniku.
Zadanie domowe