C++ · Podstawy · Bity

Liczby dwójkowe

Komputer nie zna cyfr od 0 do 9 — zna tylko zero i jedynkę. Ta strona tłumaczy, jak z dwóch znaków robi się każda liczba i skąd tak naprawdę bierze się limit int.

Filmy z OKI

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ć.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

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.

dziesietnie.cpp
// liczba 305 dziesietnie:
//
//   3     0     5
//   |     |     |
// setki dziesiatki jednosci
//  100    10     1
//
// 3*100 + 0*10 + 5*1 = 305
//
// kazda pozycja 10x wieksza
dwojkowo.cpp
// 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.

odczyt.cpp
#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;
}
▶ Wyjście programu
00001101 00000101 11111111 13

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.

na_dziesietny.cpp
// 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;
▶ Wyjście programu
13
na_dwojkowy.cpp
// 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;
▶ Wyjście programu
1101

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.

krok_po_kroku.cpp
#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;
}
▶ Wyjście programu
n=13, dzielimy przez 2 i zbieramy reszty: 13 / 2 = 6, reszta 1 6 / 2 = 3, reszta 0 3 / 2 = 1, reszta 1 1 / 2 = 0, reszta 1 Reszty od dolu do gory: 1101

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_wartosci.cpp
// 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;
}
▶ Wyjście programu
1 bitow -> 2 wartosci 8 bitow -> 256 wartosci 16 bitow -> 65536 wartosci 32 bitow -> 4294967296 wartosci
bit_znaku.cpp
// 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.

przepelnienie.cpp
#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;
}
▶ Wyjście programu
2147483647 01111111111111111111111111111111 -2147483648 10000000000000000000000000000000

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.

and_or_xor.cpp
#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
▶ Wyjście programu
1000 1110 0110
przesuniecia.cpp
#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
▶ Wyjście programu
00001010 00010100 00000010

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:

zastosowania.cpp
#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;
}
▶ Wyjście programu
nieparzysta 52 6 bit 2: tak

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.

ZapisCo robiPrzykł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.

Łatwe Z dwójkowego na dziesiętny
Wczytaj napis złożony z zer i jedynek i wypisz, jaką liczbę przedstawia. Dla 1101 odpowiedzią jest 13.
Jak to ugryźć: Idź po znakach od lewej i buduj wynik: wynik = wynik * 2 + bit. Bit dostaniesz jako s[i] - '0' — ta sama sztuczka co przy cyfrach w temacie String.
Pokaż rozwiązanie
na_dziesietny.cpp
#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;
}
Łatwe Z dziesiętnego na dwójkowy
Wczytaj liczbę naturalną i wypisz ją w zapisie dwójkowym, bez zer wiodących. Dla 13 odpowiedzią jest 1101.
Jak to ugryźć: Dziel przez 2 i zbieraj reszty — tak jak przy rozkładzie na cyfry, tylko zamiast 10 masz 2. Reszty wychodzą od końca, więc doklejaj je z przodu napisu. Uwaga na zero — pętla nie wykona się ani razu.
Pokaż rozwiązanie
na_dwojkowy.cpp
#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;
}
Łatwe Ile jedynek
Wczytaj liczbę naturalną i wypisz, ile jedynek ma w zapisie dwójkowym. Dla 13 (czyli 1101) odpowiedzią jest 3.
Jak to ugryźć: Nie musisz budować napisu. Wystarczy w pętli sprawdzać ostatni bit przez n % 2 i dzielić przez 2, licząc trafienia.
Pokaż rozwiązanie
ile_jedynek.cpp
#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;
}
Średnie Ile bitów potrzeba
Wczytaj liczbę naturalną n i wypisz, ile najmniej bitów trzeba, żeby ją zapisać. Dla 13 odpowiedzią jest 4, dla 16 — 5.
Jak to ugryźć: To po prostu długość zapisu dwójkowego — czyli ile razy da się podzielić n przez 2, zanim dojdzie do zera. Sprawdź, co Twój program robi dla zera; zero zapisujemy jednym bitem.
Pokaż rozwiązanie
ile_bitow.cpp
#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;
}
Średnie Czy to potęga dwójki
Wczytaj liczbę naturalną i sprawdź, czy jest potęgą dwójki (1, 2, 4, 8, 16, 32…). Wypisz TAK albo NIE.
Jak to ugryźć: Popatrz na zapis dwójkowy: potęgi dwójki to 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
potega_dwojki.cpp
#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;
}
Trudne Dodawanie pisemne dwójkowo
Wczytaj dwa napisy złożone z zer i jedynek (mogą mieć nawet po 100 znaków, więc nie zmieszczą się w żadnym typie liczbowym) i wypisz ich sumę — też w zapisie dwójkowym.
Jak to ugryźć: Tak jak dodawanie pisemne w szkole, tylko że przeniesienie pojawia się już przy sumie 2, a nie przy 10. Idź od końca obu napisów, sumuj bity plus przeniesienie, zapisuj suma % 2 i przenoś suma / 2. Na koniec nie zapomnij o przeniesieniu, które zostało.
Pokaż rozwiązanie
dodawanie.cpp
#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

➕
Pozycje to same podwojenia
Od prawej: 1, 2, 4, 8, 16, 32, 64, 128. Żeby odczytać liczbę dwójkową, zsumuj pozycje z jedynkami.
🔄
Zamiana to dzielenie przez 2
Ta sama sztuczka co rozkładanie liczby na cyfry z tematu Modulo — tylko dzielisz przez 2 zamiast przez 10.
📏
Każdy bit podwaja możliwości
8 bitów to 256 wartości, 16 bitów to 65 536, a 32 bity ponad 4 miliardy. Stąd biorą się zakresy typów.
➖
Jeden bit idzie na znak
int ma 32 bity, ale musi też umieć liczby ujemne — dlatego kończy się na ~2 miliardach, a nie na ~4.
💥
Przepełnienie to przeskok bitów
Dodanie jedynki do największego int przestawia wszystkie bity i wynik ląduje na dole zakresu, czyli staje się ujemny.
👁️
bitset do podglądania
cout << bitset<8>(x) pokazuje liczbę dwójkowo. Najprostszy sposób, żeby zobaczyć, co się naprawdę dzieje z bitami.

Gotowy na więcej?

Dołącz do T-Olimpians i trenuj z doświadczonymi mentorami. Zbuduj bazę, która prowadzi do finałów OI.