Ikkilik sanoq va bit amallari

Kompyuter dasturchi ko'rgan narsa bilan emas, o'zi saqlaydigan narsa bilan ishlaydi. Har qanday son, harf yoki qiymat xotirada bitlar — nol va birlar — ketma-ketligi sifatida saqlanadi. Xotirani yoqsa ham o'chirib bo'lsa ham bilmaydi: u faqat elektr zaryadi bor yoki yo'q, ikki holatdan birini saqlovchi fizik elementlar to'plami.

Bit manipulyatsiya — bitlarni to'g'ridan-to'g'ri boshqarish usuli. Bu ba'zan kodingizni tezroq qiladi, ba'zan oddiy qiladi, ba'zan esa bit tuzilmasini tushunmasdan yechib bo'lmaydigan masalalar uchun zarur. Ikkilik sanoq tizimini va bit amallarini tushunish uchun avval sonlar kompyuterda qanday saqlanishini bilish kerak.

Ikkilik sanoq tizimi

Kundalik hayotda o'nlik sanoq (decimal) ishlatamiz: har raqam o'rni uchun 10 ning darajasi.

1234 = 1×10³ + 2×10² + 3×10¹ + 4×10⁰
     = 1000 + 200 + 30 + 4

Ikkilik sanoqda (binary) asos 10 o'rniga 2:

1101₂ = 1×2³ + 1×2² + 0×2¹ + 1×2⁰
       = 8    + 4    + 0    + 1
       = 13₁₀

Har bir ikkilik raqam bit (binary digit) deyiladi. 8 bit = 1 bayt.

O'nlik → ikkilik aylantirish

Sonni 2 ga ketma-ket bo'lib, qoldiqlar olinadi — oxiridan birinchiga o'qiladi:

13 / 2 = 6  qoldiq 1
 6 / 2 = 3  qoldiq 0
 3 / 2 = 1  qoldiq 1
 1 / 2 = 0  qoldiq 1

Pastdan yuqoriga: 1101₂ = 13₁₀

Ikkilik → o'nlik aylantirish

Har bitni o'rniga mos 2 darajasiga ko'paytirib yig'iladi:

1011₂ = 1×8 + 0×4 + 1×2 + 1×1 = 11₁₀

8-bitli misollar

Decimal  Binary        Decimal  Binary
  0    = 0000 0000       8    = 0000 1000
  1    = 0000 0001       9    = 0000 1001
  2    = 0000 0010      10    = 0000 1010
  3    = 0000 0011      15    = 0000 1111
  4    = 0000 0100     127    = 0111 1111
  5    = 0000 0101     128    = 1000 0000
  6    = 0000 0110     255    = 1111 1111
  7    = 0000 0111

Salbiy sonlar: ikkilik to'ldiruvchi

Salbiy sonlar kompyuterda ikkilik to'ldiruvchi (two's complement) usulida saqlanadi. Eng yuqori bit 0 bo'lsa — musbat, 1 bo'lsa — salbiy.

-n ni hisoblash: n ning barcha bitlarini teskari qilib, 1 qo'shiladi.

3  = 0000 0011
~3 = 1111 1100   // barcha bitlar teskari (NOT)
-3 = 1111 1101   // 1 qo'shilgach

8-bitli ishorali sonlar:

 127 = 0111 1111   // maksimal musbat
   1 = 0000 0001
   0 = 0000 0000
  -1 = 1111 1111
  -2 = 1111 1110
-128 = 1000 0000   // minimal salbiy

Bu nimaga kerak? Bit masalalarida salbiy sonlar bilan ishlashda ~n = -(n+1) ekanini bilish kerak:

~5  = -6
~0  = -1
~(-1) = 0

Bit amallari

Oltita asosiy bit amali bor. Har biri bitlar ustida pozitsiyama-pozitsiya ishlaydi.

AND (`&`)

Ikkala bit ham 1 bo'lgandagina natija 1:

Qoida:  0 & 0 = 0
        0 & 1 = 0
        1 & 0 = 0
        1 & 1 = 1

Misol:
  1010 1100
& 0011 1010
----------
  0010 1000

Ishlatish: ma'lum bitlarni "o'chirish" (masking), bit tekshirish.

OR (`|`)

Kamida bitta bit 1 bo'lganda natija 1:

Qoida:  0 | 0 = 0
        0 | 1 = 1
        1 | 0 = 1
        1 | 1 = 1

Misol:
  1010 0100
| 0001 1010
----------
  1011 1110

Ishlatish: ma'lum bitlarni "yoqish" (setting bits).

XOR (`^`)

Bitlar har xil bo'lganda 1, bir xil bo'lganda 0:

Qoida:  0 ^ 0 = 0
        0 ^ 1 = 1
        1 ^ 0 = 1
        1 ^ 1 = 0

Misol:
  1010 1100
^ 0011 1010
----------
  1001 0110

Muhim xossalar:

a ^ a = 0       // sonni o'zi bilan XOR qilish → 0
a ^ 0 = a       // 0 bilan XOR qilish → o'zgarish yo'q
a ^ b ^ a = b   // kommutativ va assotsiativ

Ishlatish: takroriy element topish, bitlarni almashtirish, shifrlash.

NOT (`~`)

Barcha bitlarni teskari qiladi:

Qoida:  ~0 = 1
        ~1 = 0

Misol (8-bit):
~ 0000 1010
-----------
  1111 0101

Ishorali sonda ~n = -(n + 1):

~5 = -6
~0 = -1

Ishlatish: bitmask yaratish, to'ldiruvchi hisoblash.

Chap siljitish (`<<`)

Barcha bitlarni chap tomonga k pozitsiya siljitadi, o'ngdan 0 bitlar qo'shiladi:

1 << 0 = 0000 0001 = 1
1 << 1 = 0000 0010 = 2
1 << 2 = 0000 0100 = 4
1 << 3 = 0000 1000 = 8

Umumiy: n << k = n × 2^k

Misol:
  0000 0011  (3)
<<         2
-----------
  0000 1100  (12 = 3 × 4)

Overflow haqida: agar siljitish natijasi bit hajmiga sig'masa, yuqori bitlar tushib qoladi. 32-bitli sonda 1 << 31 ishorasiz va ishorali holatlarda farq qiladi.

O'ng siljitish (`>>`)

Barcha bitlarni o'ng tomonga k pozitsiya siljitadi:

Mantiqiy o'ng siljitish (unsigned): chapdan 0 bitlar qo'shiladi.

Arifmetik o'ng siljitish (signed): chapdan ishora biti (eng yuqori bit) nusxalanadi — salbiy son salbiy qoladi.

Musbat son uchun:
  0001 1100  (28)
>>          2
-----------
  0000 0111  (7 = 28 / 4)

Salbiy son uchun (8-bit ishorali, arifmetik siljitish):
  1111 0100  (-12)
>>           2
-----------
  1111 1101  (-3 = -12 / 4, pastga yaxlitlanadi)

Umumiy: n >> k = FLOOR(n / 2^k) ishorali sonda (arifmetik).

Keng tarqalgan bit hiylaklari

Bu operatsiyalar masalalarda qayta-qayta uchraydi.

`k`-chi bitni tekshirish

// n ning k-chi biti (0 dan boshlab) 1 mi?
IF (n >> k) & 1 = 1
    // k-chi bit 1

Misol: n = 13 = 1101, k = 2:

1101 >> 2 = 0011
0011 & 0001 = 0001 = 1 → k-chi bit 1

`k`-chi bitni 1 ga qo'yish (set)

n = n | (1 << k)

0101 | (1 << 1) = 0101 | 0010 = 0111

`k`-chi bitni 0 ga tushirish (clear)

n = n & ~(1 << k)

~(1 << 1) = ~0010 = 1101
0111 & 1101 = 0101

`k`-chi bitni almashtirish (toggle)

n = n ^ (1 << k)

0101 ^ (1 << 2) = 0101 ^ 0100 = 0001

Eng quyi `1` bitni topish

lowest_bit = n & (-n)

Nima uchun? -n = ~n + 1. n ning eng quyi 1 bitidan past barcha bitlar 0, bu bit o'zi 1. ~n da shu bit 0, pastdagilar 1. ~n + 1 da shu bit yana 1 ga aylanadi. AND qilinganda faqat shu bit qoladi:

n  = 0110 1100
-n = 1001 0100
n & (-n) = 0000 0100   // eng quyi 1 bit

Eng quyi `1` bitni o'chirish

n = n & (n - 1)

n     = 0110 1100
n - 1 = 0110 1011
n & (n-1) = 0110 1000   // eng quyi 1 bit o'chirildi

Bu operatsiya n ning barcha 1 bitlarini sanash uchun (Brian Kernighan algoritmi) ishlatiladi.

Ikki darajasi tekshirish

n > 0 VA n & (n - 1) = 0

Ikki darajasi binarda faqat bitta 1 bit. n - 1 esa shu bitni 0 ga, pastdagilarni 1 ga aylantiradi. AND nol beradi.

Ikkita sonni almashtirish (swap)

a = a ^ b
b = a ^ b   // b = (a ^ b) ^ b = a
a = a ^ b   // a = (a ^ b) ^ a = b

Qo'shimcha o'zgaruvchisiz. Ammo a va b bir xil xotira manzili bo'lsa — muammo bo'ladi. Amalda bu usul odatda qo'shimcha o'zgaruvchi bilan swap'dan sekinroq bo'lishi mumkin (CPU pipelining sabab).

Hexadecimal (o'n oltilik) sanoq

Bit naqshlarini o'nlik bilan ifodalash noqulay bo'lganda hex ishlatiladi. 4 bit = 1 hex raqam:

0000 = 0    0100 = 4    1000 = 8    1100 = C
0001 = 1    0101 = 5    1001 = 9    1101 = D
0010 = 2    0110 = 6    1010 = A    1110 = E
0011 = 3    0111 = 7    1011 = B    1111 = F

8-bitli 1111 0101 → F5 (hex). Kodda odatda 0xFF, 0x1A2B ko'rinishida yoziladi.

Murakkablik

Bit amallari O(1) — protsessor bir instruksiyada bajaradi. Bu ularni ko'p sonlar ustida ishlashda juda samarali qiladi. Bitmask bilan n ta elementni bitta butun sonda kodlash va barchani O(1) da tekshirish — kichik n uchun keng qo'llaniladigan usul.

Keng tarqalgan xatolar

Operator ustunligini bilmaslik

&, |, ^ operatorlari ko'p tillarda qo'shish/ayirish va taqqoslashdan past ustunlikda. Qavslar zarur:

// Noto'g'ri:
IF n & 1 = 1    // bu IF n & (1 = 1) kabi tushunilishi mumkin

// To'g'ri:
IF (n & 1) = 1

Chap siljitishda overflow

1 << 31 32-bitli ishorali sonda implementation-defined. Katta siljitish uchun kattaroq tipga o'tish yoki ishlatilayotgan tilning xatti-harakatini bilish kerak.

O'ng siljitish va manfiy son

Arifmetik o'ng siljitish manfiy sonni pastga yaxlitlab bo'ladi. (-7) >> 1 = -4, lekin -7 / 2 = -3 (truncation). Bu farqni bilmaslik xatoga olib keladi.

`~n` va `-(n+1)` ni aralashtirish

~n bit darajasida NOT — barcha bitlarni teskari. Ishorali sonda ~n = -(n+1). ~0 = -1, ~(-1) = 0. Bu noto'g'ri ishlatilsa mantiqiy xato chiqaradi.

Bir xil o'zgaruvchi bilan XOR swap

// a va b bir xil bo'lsa (a = b yoki xotira manzili bir xil):
a = a ^ a = 0
b = 0 ^ a = a   // endi b = 0, a o'zgarishi kerak edi
a = 0 ^ 0 = 0   // xato!

Qachon bit manipulyatsiya kerak?

Bit manipulyatsiya har masalada kerak emas. Quyidagi holatlarda foydali:

Bir nechta bayroq (flag) yoki holat bitlar bilan ifodalansa
n < 64 element to'plami bitmask sifatida ishorali yoki ishorasiz 64-bitli sonda kodlansa
Ikki darajasi, XOR xossasi, bit soni kabi matematik xossalar masalaning asosi bo'lsa
Arifmetika o'rniga tezroq bit alternativ bo'lsa (eng quyi bit, ko'paytma/bo'lish o'rniga siljitish)

Note

Bit manipulyatsiya kodni qisqartirishi mumkin, lekin o'qilishini qiyinlashtirishi ham mumkin. Agar bit hiylasi kodning maqsadini yashirib qo'ysa — oddiy yondashuv yaxshiroq.

Xulosa

Ikkilik sanoq kompyuterning asosiy tili. Har son bitlar ketma-ketligi. Ishorali sonlar ikkilik to'ldiruvchi usulida saqlanadi — bu ~n = -(n+1) aloqasini beradi.

Olti bit amali — AND, OR, XOR, NOT, <<, >> — bitlarni to'g'ridan-to'g'ri boshqaradi. Ular asosida: bit tekshirish, o'rnatish, o'chirish, almashtirish, eng quyi bit, ikki darajasi tekshirish va XOR xossalari kelib chiqadi.

Keyingi bo'limlarda bu amallar asosidagi masalalar ko'riladi.