Bitli amallar
Bitli amallar butun sonlarning ikkilik ko‘rinishi ustida bevosita ishlaydi.
| Operator | Belgi | Misol | Ma’nosi |
|---|---|---|---|
| Bitli chapga siljitish | << | x << k | x ning barcha bitlarini chapga k pozitsiyaga siljitadi |
| Bitli o‘ngga siljitish | >> | x >> k | x ning barcha bitlarini o‘ngga k pozitsiyaga siljitadi |
| Bitli AND | & | x & y | Mos keluvchi bitlarning har bir juftiga AND qo‘llaydi |
| Bitli OR | | | x | y | Mos keluvchi bitlarning har bir juftiga OR qo‘llaydi |
| Bitli eksklyuziv OR | ^ |
x ^ y |
| Mos keluvchi bitlarning har bir juftiga XOR qo‘llaydi |
Ikkilik sonni
chapga pozitsiyaga siljitganda, o‘ng tomonga ta nol qo‘shamiz:
Shuning uchun chapga bir pozitsiyaga siljitish ga ko‘paytirishga teng, chapga pozitsiyaga siljitish esa ga ko‘paytirishga teng.
Chiqish:
Ikkilik sonni
o‘ngga pozitsiyaga siljitganda, oxirgi ta bit olib tashlanadi:
Manfiy bo‘lmagan butun sonlar uchun o‘ngga bir pozitsiyaga siljitish ga butun bo‘lishga teng, o‘ngga pozitsiyaga siljitish esa ga butun bo‘lishga teng.
Chiqish:
Ikki sonning va bitli AND amali natijasi son bo‘lib, bunda
Bu mos keluvchi bitlarning har bir juftiga AND qo‘llashimizni anglatadi.
x & y natijasi faqat ikkala bit ham 1 bo‘lsa 1 bo‘ladi. Aks holda 0.
| x | y | Natija |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Chiqish:
Ikki sonning va bitli OR amali natijasi son bo‘lib, bunda
Bu mos keluvchi bitlarning har bir juftiga OR qo‘llashimizni anglatadi.
x | y natijasi bitlardan kamida bittasi 1 bo‘lsa 1 bo‘ladi. Aks holda 0.
| x | y | Natija |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Chiqish:
Ikki sonning va bitli XOR amali natijasi son bo‘lib, bunda
Bu mos keluvchi bitlarning har bir juftiga XOR qo‘llashimizni anglatadi.
x ^ y natijasi bitlardan aniq bittasi 1 bo‘lsa 1 bo‘ladi. Agar ikkala bit bir xil bo‘lsa, natija 0.
| x | y | Natija |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Chiqish:
Yechimlarga qarashdan oldin bu masalalarni o‘zingiz yechib ko‘ring.
Ikki butun son va berilgan, bunda , quyidagi qiymatni chiqaring:
Ikki butun son va berilgan, sonining -chi bitini invert qilgandan keyin hosil bo‘lgan sonni chiqaring.
Ikki butun son va berilgan, sonining -chi bitini 0 ga o‘rnatgandan keyin hosil bo‘lgan sonni chiqaring.
Ikki butun son va berilgan, sonining -chi bitining qiymatini chiqaring.
Ikki butun son va berilgan, sonining oxirgi ta bitini 0 ga o‘rnating va natijani chiqaring.
Ikki butun son va berilgan, *, /, yoki % amallaridan foydalanmasdan ularning ko‘paytmasini hisoblang.
ni olish uchun 1 << x dan foydalanishimiz mumkin. Xuddi shunday, 1 << y ni beradi.
bo‘lgani uchun, bu ikki sonning o‘rnatilgan yagona bitlari turlicha, shuning uchun ularni bitli OR bilan birlashtirishimiz mumkin.
-chi bitni invert qilish uchun faqat -chi biti 1 bo‘lgan maska bilan XOR ishlatamiz.
-chi bitni 0 ga o‘rnatish uchun avval u 1 ekanligini tekshirishimiz mumkin. Agar shunday bo‘lsa, uni aylantiramiz.
Qisqaroq variant:
-chi bitning qiymatini olish uchun uni oxirgi pozitsiyaga siljitamiz va oxirgi bitni olamiz.
Sikl bilan yechim
Oxirgi ta bitni birma-bir tekshiramiz va kerak bo‘lsa ularni tozalaymiz.
Siklsiz yechim
Sonni o‘ngga bitga siljitamiz, bu oxirgi ta bitni olib tashlaydi, so‘ng uni yana chapga bitga siljitamiz.
ning ikkilik ko‘rinishidan foydalanishimiz mumkin.
Agar ning -chi biti 1 bo‘lsa, unda ni qo‘shamiz, bu x << i bilan bir xil.
int x = 11; // x = 1011 in binary
cout << (x << 2) << "\n"; // 101100 in binary
int x = 11; // x = 1011 in binary
cout << (x >> 2) << "\n"; // 10 in binary
int x = 11; // x = 1011
int y = 6; // y = 0110
cout << (x & y) << "\n"; // 0010 in binary
int x = 9; // x = 1001
int y = 4; // y = 0100
cout << (x | y) << "\n"; // 1101 in binary
int x = 12; // x = 1100
int y = 6; // y = 0110
cout << (x ^ y) << "\n"; // 1010 in binary
cout << ((1 << x) | (1 << y)) << "\n";
cout << (x ^ (1 << k)) << "\n";
if (x & (1 << k)) {
x ^= (1 << k);
}
cout << x << "\n";
cout << (x & (~(1 << k))) << "\n";
cout << ((x >> k) & 1) << "\n";
for (int i = 0; i < k; i++) {
if (x & (1 << i)) {
x ^= (1 << i);
}
}
cout << x << "\n";
cout << ((x >> k) << k) << "\n";
long long res = 0;
for (int i = 0; i < 30; i++) {
if (y & (1 << i)) {
res += (1LL * x << i);
}
}
cout << res << "\n";