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
Bitli Chapga Siljitish
Ikkilik sonni
(an−1an−2…a1a0)2
chapga k pozitsiyaga siljitganda, o‘ng tomonga k ta nol qo‘shamiz:
(an−1an−2…a1a000…0)2
Shuning uchun chapga bir pozitsiyaga siljitish 2 ga ko‘paytirishga teng, chapga k pozitsiyaga siljitish esa 2k ga ko‘paytirishga teng.
Chiqish:
44
Bitli O‘ngga Siljitish
Ikkilik sonni
(an−1an−2…a1a0)2
o‘ngga k pozitsiyaga siljitganda, oxirgi k ta bit olib tashlanadi:
(an−1an−2…ak)2
Manfiy bo‘lmagan butun sonlar uchun o‘ngga bir pozitsiyaga siljitish 2 ga butun bo‘lishga teng, o‘ngga k pozitsiyaga siljitish esa 2k ga butun bo‘lishga teng.
Chiqish:
2
Bitli AND
Ikki sonning (a)2 va (b)2 bitli AND amali natijasi (c)2 son bo‘lib, bunda
ci=ai&bi
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.
AND jadvali
x
y
Natija
0
0
0
0
1
0
1
0
0
1
1
1
Chiqish:
2
Bitli OR
Ikki sonning (a)2 va (b)2 bitli OR amali natijasi (c)2 son bo‘lib, bunda
ci=ai∣bi
Bu mos keluvchi bitlarning har bir juftiga OR qo‘llashimizni anglatadi.
x | y natijasi bitlardan kamida bittasi1 bo‘lsa 1 bo‘ladi. Aks holda 0.
OR jadvali
x
y
Natija
0
0
0
0
1
1
1
0
1
1
1
1
Chiqish:
13
Bitli Eksklyuziv OR (XOR)
Ikki sonning (a)2 va (b)2 bitli XOR amali natijasi (c)2 son bo‘lib, bunda
ci=ai⊕bi
Bu mos keluvchi bitlarning har bir juftiga XOR qo‘llashimizni anglatadi.
x ^ y natijasi bitlardan aniq bittasi1 bo‘lsa 1 bo‘ladi. Agar ikkala bit bir xil bo‘lsa, natija 0.
XOR jadvali
x
y
Natija
0
0
0
0
1
1
1
0
1
1
1
0
Chiqish:
10
Misol Masalalar
Yechimlarga qarashdan oldin bu masalalarni o‘zingiz yechib ko‘ring.
Misol 1
Ikki butun son x(0≤x≤29) va y(0≤y≤29) berilgan, bunda x=y, quyidagi qiymatni chiqaring:
2x+2y
Misol 2
Ikki butun son x(0≤x≤229) va k(0≤k≤29) berilgan, x sonining k-chi bitini invert qilgandan keyin hosil bo‘lgan sonni chiqaring.
Misol 3
Ikki butun son x(0≤x≤229) va k(0≤k≤29) berilgan, x sonining k-chi bitini 0 ga o‘rnatgandan keyin hosil bo‘lgan sonni chiqaring.
Misol 4
Ikki butun son x(0≤x≤229) va k(0≤k≤29) berilgan, x sonining k-chi bitining qiymatini chiqaring.
Misol 5
Ikki butun son x(0≤x≤229) va k(0≤k≤29) berilgan, x sonining oxirgi k ta bitini 0 ga o‘rnating va natijani chiqaring.
Misol 6
Ikki butun son x(0≤x≤109) va y(0≤y≤109) berilgan, *, /, yoki % amallaridan foydalanmasdan ularning ko‘paytmasini hisoblang.
Misollarning Yechimlari
Misol 1
2x ni olish uchun 1 << x dan foydalanishimiz mumkin. Xuddi shunday, 1 << y2y ni beradi.
x=y bo‘lgani uchun, bu ikki sonning o‘rnatilgan yagona bitlari turlicha, shuning uchun ularni bitli OR bilan birlashtirishimiz mumkin.
Misol 2
k-chi bitni invert qilish uchun faqat k-chi biti 1 bo‘lgan maska bilan XOR ishlatamiz.
Misol 3
k-chi bitni 0 ga o‘rnatish uchun avval u 1 ekanligini tekshirishimiz mumkin. Agar shunday bo‘lsa, uni aylantiramiz.
Qisqaroq variant:
Misol 4
k-chi bitning qiymatini olish uchun uni oxirgi pozitsiyaga siljitamiz va oxirgi bitni olamiz.
Misol 5
Sikl bilan yechim
Oxirgi k ta bitni birma-bir tekshiramiz va kerak bo‘lsa ularni tozalaymiz.
Siklsiz yechim
Sonni o‘ngga k bitga siljitamiz, bu oxirgi k ta bitni olib tashlaydi, so‘ng uni yana chapga k bitga siljitamiz.
Misol 6
y ning ikkilik ko‘rinishidan foydalanishimiz mumkin.
Agar y ning i-chi biti 1 bo‘lsa, unda x⋅2i ni qo‘shamiz, bu x << i bilan bir xil.
int x = 11; // x = 1011 in binarycout <<(x << 2)<< "\n"; // 101100 in binary
int x = 11; // x = 1011 in binarycout <<(x >> 2)<< "\n"; // 10 in binary
int x = 11; // x = 1011int y = 6; // y = 0110cout <<(x & y)<< "\n"; // 0010 in binary
int x = 9; // x = 1001int y = 4; // y = 0100cout <<(x | y)<< "\n"; // 1101 in binary
int x = 12; // x = 1100int y = 6; // y = 0110cout <<(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";