Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 3 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.
Dlaczego akurat dwie cyfry?
W środku komputera nie ma żadnych cyfr. Jest prąd, który przez dany przewodzik płynie albo nie płynie — i to wszystko, co potrafi rozróżnić. Dwa stany to dwie cyfry: 0 i 1. Jedno takie miejsce nazywa się bitem.
Z jednym bitem daleko nie zajedziesz — zapiszesz tylko zero albo jeden. Ale bity ustawia się obok siebie, dokładnie tak jak cyfry w zwykłej liczbie. I tak samo jak u nas każda pozycja jest dziesięć razy większa od poprzedniej, tam każda jest dwa razy większa.
// liczba 305 dziesietnie:
//
// 3 0 5
// | | |
// setki dziesiatki jednosci
// 100 10 1
//
// 3*100 + 0*10 + 5*1 = 305
//
// kazda pozycja 10x wieksza
// liczba 1101 dwojkowo:
//
// 1 1 0 1
// | | | |
// 8 4 2 1
//
// 1*8 + 1*4 + 0*2 + 1*1 = 13
//
// kazda pozycja 2x wieksza
To jest cała tajemnica. Pozycje od prawej to kolejno 1, 2, 4, 8, 16, 32, 64, 128 i tak dalej — same podwojenia. Żeby odczytać liczbę dwójkową, zsumuj wartości pozycji, na których stoi jedynka.
bit
Jedno miejsce: zero albo jeden. Najmniejsza porcja informacji, jaką komputer rozróżnia.
bajt
Osiem bitów obok siebie. Mieści 256 różnych wartości, czyli liczby od 0 do 255.
pozycje
Od prawej: 1, 2, 4, 8, 16, 32, 64, 128… każda kolejna dwa razy większa.
odczyt
Zsumuj pozycje, na których stoi jedynka. 1101 to 8+4+1, czyli 13.
kolejność
Bit najbardziej po prawej to ten najmniejszy, wart 1 — tak jak cyfra jedności.
ile bitów
int to 32 bity, long long — 64. Stąd biorą się ich zakresy.
#include <iostream>
#include <bitset>
using namespace std;
int main() {
// C++ potrafi pokazac liczbe dwojkowo
cout << bitset<8>(13) << "\n"; // 00001101
cout << bitset<8>(5) << "\n"; // 00000101
cout << bitset<8>(255) << "\n"; // 11111111
// i odczytac ja z napisu
cout << bitset<8>("00001101").to_ulong();
return 0;
}
Z dziesiętnego na dwójkowy i z powrotem
Zamiana z dwójkowego na dziesiętny to zwykłe sumowanie, o którym była mowa wyżej. Ciekawsza jest droga w drugą stronę — i okazuje się, że to dokładnie ta sama sztuczka, której użyłeś w temacie Modulo do rozkładania liczby na cyfry.
Tam dzieliłeś przez 10 i zbierałeś reszty, żeby dostać cyfry dziesiętne. Tutaj dzielisz przez 2 i zbierasz reszty — i dostajesz bity. Jedyna różnica to liczba, przez którą dzielisz.
// 1101 -> 13
int bity[4] = {1, 1, 0, 1}; // od lewej
int wynik = 0;
for (int i = 0; i < 4; i++) {
wynik = wynik * 2 + bity[i];
}
cout << wynik;
// 13 -> 1101
int n = 13;
string wynik = "";
while (n > 0) {
wynik = char('0' + n % 2) + wynik;
n /= 2; // tak jak /= 10 przy cyfrach
}
cout << wynik;
Zwróć uwagę na wynik = ... + wynik w prawym przykładzie: nowy bit doklejamy z przodu, bo reszty wychodzą od najmniejszej pozycji. Gdybyśmy doklejali z tyłu, dostalibyśmy liczbę zapisaną od tyłu.
#include <iostream>
using namespace std;
int main() {
int n = 13;
cout << "n=13, dzielimy przez 2 i zbieramy reszty:\n\n";
while (n > 0) {
cout << n << " / 2 = " << n / 2
<< ", reszta " << n % 2 << "\n";
n /= 2;
}
cout << "\nReszty od dolu do gory: 1101";
return 0;
}
Dlaczego int kończy się na 2 miliardach
W temacie o typach zmiennych przyjąłeś na wiarę, że int kończy się w okolicach dwóch miliardów. Teraz możesz to policzyć sam.
Na jednym bicie zapiszesz 2 różne wartości. Na dwóch — 4 (bo do każdej wartości pierwszego bitu dochodzą dwie możliwości drugiego). Na trzech — 8. Każdy dodatkowy bit podwaja liczbę możliwości.
// ile roznych liczb zapisze na n bitach
#include <iostream>
using namespace std;
int main() {
long long ile = 1;
for (int bitow = 1; bitow <= 32; bitow++) {
ile *= 2;
if (bitow == 1 || bitow == 8 ||
bitow == 16 || bitow == 32) {
cout << bitow << " bitow -> "
<< ile << " wartosci\n";
}
}
return 0;
}
// int ma 32 bity = 4 294 967 296 wartosci
//
// ale musi tez umiec liczby UJEMNE,
// wiec jeden bit idzie na znak:
//
// polowa wartosci -> liczby ujemne
// polowa wartosci -> zero i dodatnie
//
// 4 294 967 296 / 2 = 2 147 483 648
//
// stad zakres int:
// od -2 147 483 648
// do 2 147 483 647
//
// (o jeden mniej z gory, bo zero
// zajmuje miejsce po stronie dodatniej)
I to jest cała odpowiedź. int ma 32 bity, z czego jeden idzie na znak — zostaje 31 bitów na samą wartość, czyli nieco ponad dwa miliardy w każdą stronę. long long ma 64 bity, więc jego zakres to około 9 trylionów.
Wynika stąd też coś, co wcześniej wyglądało tajemniczo: przepełnienie. Gdy do największego int dodasz jeden, wszystkie bity przeskakują — i wynik ląduje na samym dole zakresu, czyli staje się ujemny. To nie jest usterka, tylko naturalna konsekwencja tego, że bitów jest skończenie wiele.
#include <iostream>
#include <climits>
#include <bitset>
using namespace std;
int main() {
int maks = INT_MAX;
cout << maks << "\n";
cout << bitset<32>(maks) << "\n\n";
cout << maks + 1 << "\n";
cout << bitset<32>(maks + 1) << "\n";
return 0;
}
Sześć znaków, które działają na bitach
Skoro liczba to ciąg bitów, można na tych bitach działać wprost. C++ ma na to sześć znaków. Trzy pierwsze działają dokładnie jak &&, || i ! z tematu o warunkach — tylko że osobno dla każdej pary bitów.
#include <bitset>
int a = 12; // 1100
int b = 10; // 1010
// & - jedynka tam, gdzie OBA maja jedynke
cout << bitset<4>(a & b) << "\n"; // 1000 = 8
// | - jedynka tam, gdzie CHOC JEDEN ma
cout << bitset<4>(a | b) << "\n"; // 1110 = 14
// ^ - jedynka tam, gdzie DOKLADNIE JEDEN
cout << bitset<4>(a ^ b) << "\n"; // 0110 = 6
#include <bitset>
int x = 5; // 00000101
// << przesuwa bity w lewo = MNOZY przez 2
cout << bitset<8>(x << 1) << "\n"; // 00001010 = 10
cout << bitset<8>(x << 2) << "\n"; // 00010100 = 20
// >> przesuwa w prawo = DZIELI przez 2
cout << bitset<8>(x >> 1) << "\n"; // 00000010 = 2
Przesunięcia są najbardziej intuicyjne: dopisanie zera z prawej strony mnoży liczbę przez dwa, dokładnie tak jak dopisanie zera do liczby dziesiętnej mnoży ją przez dziesięć. x << 3 to to samo co x * 8.
Do czego to się przydaje w praktyce? Trzy rzeczy spotkasz najczęściej:
#include <iostream>
using namespace std;
int main() {
int x = 13;
// 1. parzystosc - patrzymy na ostatni bit
// (to samo co x % 2, tylko krocej)
if (x & 1) cout << "nieparzysta\n";
else cout << "parzysta\n";
// 2. mnozenie i dzielenie przez potegi dwojki
cout << (x << 2) << "\n"; // 13 * 4 = 52
cout << (x >> 1) << "\n"; // 13 / 2 = 6
// 3. sprawdzenie konkretnego bitu
// czy bit numer 2 (wart 4) jest ustawiony?
if (x & (1 << 2)) cout << "bit 2: tak\n";
else cout << "bit 2: nie\n";
return 0;
}
Nie musisz tego używać. Wszystko powyżej da się napisać przez % i * — i na początku tak rób, bo jest czytelniej. Warto to jednak rozpoznać, gdy zobaczysz w cudzym kodzie, a przy okazji to najlepszy wstęp do tematu Bitset, który jest tuż obok.
Bity w jednym miejscu
Pierwsze cztery wiersze to sama zamiana liczb, reszta to działania na bitach. Na początku wystarczy Ci górna połowa.
| Zapis | Co robi | Przykład |
|---|---|---|
bitset<8>(x) |
Pokazuje liczbę dwójkowo. | 13 → 00001101 |
bitset<8>(s).to_ulong() |
Zamienia napis z zerami i jedynkami na liczbę. | "1101" → 13 |
n % 2, n /= 2 |
Kolejne bity od najmniejszego. | Jak rozkład na cyfry |
w = w * 2 + bit |
Buduje liczbę z bitów od lewej. | 1101 → 13 |
a & b |
Jedynka tam, gdzie oba mają jedynkę. | 12 & 10 = 8 |
a | b |
Jedynka tam, gdzie choć jeden ma. | 12 | 10 = 14 |
a ^ b |
Jedynka tam, gdzie dokładnie jeden ma. | 12 ^ 10 = 6 |
~a |
Odwraca wszystkie bity. | — |
x << k |
Przesuwa bity w lewo — mnoży przez 2 do k. |
5 << 2 = 20 |
x >> k |
Przesuwa w prawo — dzieli przez 2 do k. |
20 >> 2 = 5 |
x & 1 |
Sprawdza ostatni bit — czyli parzystość. | To samo co x % 2 |
x & (1 << k) |
Sprawdza, czy bit numer k jest ustawiony. |
13 & 4 → prawda |
Ostatnie dwa wiersze wyglądają tajemniczo, ale robią proste rzeczy. 1 << k to liczba, która ma jedynkę tylko na pozycji k — a & sprawdza, czy nasza liczba też ją tam ma. Na początku spokojnie używaj zwykłego % i *; te zapisy warto po prostu rozpoznać w cudzym kodzie.
Sprawdź się na zadaniach
Sześć zadań od najprostszego. Pierwsze trzy to sama zamiana liczb, dalsze dotykają bitów. Wszystkie da się zrobić bez żadnych gotowych funkcji — najpierw spróbuj sam.
1101 odpowiedzią jest 13.wynik = wynik * 2 + bit. Bit dostaniesz jako s[i] - '0' — ta sama sztuczka co przy cyfrach w temacie String.Pokaż rozwiązanie
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
long long wynik = 0;
for (int i = 0; i < s.length(); i++) {
wynik = wynik * 2 + (s[i] - '0');
}
cout << wynik;
return 0;
}
13 odpowiedzią jest 1101.Pokaż rozwiązanie
#include <iostream>
#include <string>
using namespace std;
int main() {
long long n;
cin >> n;
if (n == 0) {
cout << 0;
return 0;
}
string wynik = "";
while (n > 0) {
wynik = char('0' + n % 2) + wynik;
n /= 2;
}
cout << wynik;
return 0;
}
13 (czyli 1101) odpowiedzią jest 3.n % 2 i dzielić przez 2, licząc trafienia.Pokaż rozwiązanie
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
int ile = 0;
while (n > 0) {
if (n % 2 == 1) ile++;
n /= 2;
}
cout << ile;
return 0;
}
n i wypisz, ile najmniej bitów trzeba, żeby ją zapisać. Dla 13 odpowiedzią jest 4, dla 16 — 5.n przez 2, zanim dojdzie do zera. Sprawdź, co Twój program robi dla zera; zero zapisujemy jednym bitem.Pokaż rozwiązanie
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
if (n == 0) {
cout << 1;
return 0;
}
int bitow = 0;
while (n > 0) {
bitow++;
n /= 2;
}
cout << bitow;
return 0;
}
TAK albo NIE.1, 10, 100, 1000… czyli liczby z dokładnie jedną jedynką. Wystarczy policzyć jedynki z poprzedniego zadania. Pamiętaj, że zero potęgą dwójki nie jest.Pokaż rozwiązanie
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
if (n <= 0) {
cout << "NIE";
return 0;
}
int jedynek = 0;
while (n > 0) {
if (n % 2 == 1) jedynek++;
n /= 2;
}
cout << (jedynek == 1 ? "TAK" : "NIE");
return 0;
}
suma % 2 i przenoś suma / 2. Na koniec nie zapomnij o przeniesieniu, które zostało.Pokaż rozwiązanie
#include <iostream>
#include <string>
using namespace std;
int main() {
string a, b;
cin >> a >> b;
string wynik = "";
int i = a.length() - 1;
int j = b.length() - 1;
int przeniesienie = 0;
while (i >= 0 || j >= 0 || przeniesienie > 0) {
int suma = przeniesienie;
if (i >= 0) suma += a[i--] - '0';
if (j >= 0) suma += b[j--] - '0';
wynik = char('0' + suma % 2) + wynik;
przeniesienie = suma / 2;
}
cout << wynik;
return 0;
}
Częste błędy i dobre praktyki
1, 2, 4, 8, 16, 32, 64, 128. Żeby odczytać liczbę dwójkową, zsumuj pozycje z jedynkami.int ma 32 bity, ale musi też umieć liczby ujemne — dlatego kończy się na ~2 miliardach, a nie na ~4.int przestawia wszystkie bity i wynik ląduje na dole zakresu, czyli staje się ujemny.cout << bitset<8>(x) pokazuje liczbę dwójkowo. Najprostszy sposób, żeby zobaczyć, co się naprawdę dzieje z bitami.