Bit manipulyatsiya masalalari: XOR hiylasi, bitlarni sanash va bitmask

Qisqacha: Bitli amallar ba'zi masalalarni qo'shimcha xotirasiz va juda tez yechadi. XOR (^) bir xil sonlarni bir-birini yo'q qiladi: hamma elementni XOR qilsangiz, faqat juftsizi qoladi. Ifoda n & (n - 1) sonning eng o'ngdagi 1 bitini o'chiradi — u bilan 1 larni sanash va 2 ning darajasini tekshirish mumkin. Bitmask esa 0 dan 2ⁿ − 1 gacha sanab, n ta elementning hamma to'plamini rekursiyasiz ko'rib chiqadi.

Bu darsda

• XOR xususiyatlaridan foydalanib, juftsiz elementni O(n) vaqt va O(1) xotirada topa olasiz.
• n & (n - 1) nima qilishini bit darajasida tushuntira olasiz va u bilan 1 larni sanaysiz.
• Son 2 ning darajasi ekanini bitta ifoda bilan tekshira olasiz.
• Bitmask bilan hamma qism-to'plamlarni ko'rib chiqasiz va bu usulning chegaralarini (32 bit, 2ⁿ) bilasiz.

Oldin bilishingiz kerak: Bitwise operatorlar va bit bayroqlar, Klassik chiziqli algoritmlar, Asosiy murakkablik sinflari.

1. Nega bu kerak?

Bitwise operatorlar darsida bitlarni ruxsatlar uchun ishlatgan edik: bitta sonda "o'qish", "yozish", "o'chirish" bayroqlari. O'sha dars oxirida va'da bergan edik: intervyudagi "n & 1 nima qiladi?", "son 2 ning darajasimi?" kabi savollarga shu darsda tayyorlanamiz. Bugun bitlarni algoritm uchun ishlatamiz.

«Bahor»da kechki tekshiruv bor. Har chek ikki joyda qayd qilinadi: kassada va oshxonada. Kun oxirida ikki ro'yxat birlashtiriladi — har raqam ikki martadan uchrashi kerak. Bugun bitta chek faqat bir marta uchradi: qaysidir buyurtma oshxonaga yetib bormagan. Sardor uni topishi kerak. Ro'yxatda yuz minglab raqam bo'lishi mumkin.

Ikkinchi masala: Jasur aka "set menyu" tuzmoqchi. Menyudan bir nechta taom tanlanadi, narxi aniq 63 000 so'm bo'lishi kerak. Qaysi to'plamlar mos keladi? Bugungi darsda ikkala masala ham bitlar bilan, qisqa va tez yechiladi.

2. XOR hiylasi: juftsiz element

2.1 Sodda yechimlar

Eng birinchi yo'l — hash map bilan sanash: har raqam necha marta uchraganini Map ga yozamiz, keyin 1 marta uchraganini qidiramiz. Vaqt O(n), lekin xotira O(n) — yarim million yozuv. Ikkinchi yo'l — saralab, qo'shnilarni solishtirish: O(n log n) vaqt. Uchinchi yo'l — har raqamni qolganlari bilan solishtirish: O(n²).

Bitlar bilan bundan yaxshiroq qilsa bo'ladi: O(n) vaqt va bitta son xotira.

2.2 XOR'ning to'rt xususiyati

XOR (^) ni Bitwise operatorlar darsidan eslang: bitlar har xil bo'lsa 1, bir xil bo'lsa 0. Bundan to'rtta foydali xususiyat kelib chiqadi:

Oxirgi ikki xususiyat muhim: XOR zanjirida sonlarni istalgan tartibda qayta joylashtirish mumkin. Demak, 104 ^ 107 ^ 104 ^ 109 ^ 107 ni (104 ^ 104) ^ (107 ^ 107) ^ 109 deb o'qish mumkin. Juftlar nolga aylanadi, 0 ^ 0 ^ 109 — 109.

2.3 Yechim va vizual

Hamma raqamlarni bitta o'zgaruvchiga XOR qilib boramiz. Har qadamda ikkilik ko'rinishga qarang — juftlar oraliq natijani "chalkashtiradi", lekin oxirida hammasi o'chadi:

O'rtadagi qadamlarda acc ma'nosiz sonlar (3, 107, 6) bo'lib ko'rinadi. Bundan qo'rqmang: XOR "hisobni" bitlarda saqlaydi. Har bit ustunida 1 lar soni juft bo'lsa — 0, toq bo'lsa — 1. Juftsiz raqamning bitlari oxirida yolg'iz qoladi.

Murakkablik: bitta sikl — O(n) vaqt, bitta son — O(1) xotira. Boyer-Moore kabi bu ham "bir o'tish + bir o'zgaruvchi" naqshi.

2.4 O'lchov: XOR va Map

Ikkala yechimni olcha usuli bilan o'lchadik. Kirish — n ta raqam (hammasi juft, bittasi juftsiz), urug'li generator bilan aralashtirilgan:

Ikkalasida ham n ikki baravar — vaqt taxminan ikki baravar: ikkalasi O(n). Lekin Map taxminan 30 baravar sekin: har raqam uchun xesh hisoblash, yozuv yaratish, xotiradan joy olish bor. Big-O bir xil, o'zgarmas ko'paytuvchi esa juda farq qiladi (Big-O notatsiyasi darsidagi kabi).

2.5 Tuzoq: 32 bit

Bitli operatorlar sonni 32 bitli butun songa aylantiradi (Bitwise operatorlar, "32 bit qoidasi"). Chek raqamlari 2 147 483 647 dan katta bo'lsa, natija buziladi:

let acc = 0;
for (const r of [5000000001, 5000000003, 5000000001]) acc ^= r;
console.log(acc); // 705032707

To'g'ri javob 5 000 000 003, lekin chiqdi 705 032 707. Xato xabari yo'q — faqat noto'g'ri son. Katta butun sonlar uchun BigInt ishlating: 5000000001n ^ 5000000003n ^ 5000000001n — 5000000003n. Yoki raqamlarni satr sifatida Map bilan sanang.

Tekshirib ko'ring: Ro'yxatda har raqam uch martadan, bittasi bir marta uchrasa, XOR hiylasi ishlaydimi? [3, 3, 3, 5] ni sinang.

3. Bitlarni sanash

3.1 Masala

Bron tizimida mehmonning haftalik jadvali bitmask bilan saqlanadi: 7 bit — 7 kun, 1 — shu kuni bron bor. 90 = 1011010 — to'rt kun. Sonda nechta 1 bitini sanash — bitlarni sanash (popcount, population count) deyiladi.

Sodda yo'llar ikkita. Birinchisi — satrga aylantirib, 1 larni sanash: (90).toString(2).replaceAll("0", "").length — 4. Ishlaydi, lekin har safar yangi satr yaratadi. Ikkinchisi — 32 bitning hammasini birma-bir tekshirish: n & 1 bilan oxirgi bitni olib, n >>>= 1 bilan siljitish. Bu doim 32 qadam (yoki eng chapdagi 1 gacha).

3.2 n & (n - 1) nima qiladi

Bitta ayirishga qarang. n - 1 da nima bo'ladi? Eng o'ngdagi 1 bit 0 ga aylanadi, undan o'ngdagi hamma 0 lar esa 1 ga:

O'nlik sanoqdagi kabi: 1000 − 1 = 999 — oxirgi nol bo'lmagan raqam bittaga kamayadi, o'ngdagi nollar to'qqizga aylanadi. Ikkilikda "to'qqiz" — 1. Endi & qilsak: o'zgargan bitlarning hammasi bir-biriga qarama-qarshi — ular 0 bo'ladi. Qolgan bitlar o'zgarmagan — o'zicha qoladi. Natija: eng o'ngdagi 1 o'chdi, boshqa hech narsa o'zgarmadi.

3.3 Kernighan usuli

Demak, n & (n - 1) ni n nolga aylanguncha takrorlasak, sikl aynan 1 lar soni qadar aylanadi. Bu usul Brian Kernighan nomi bilan mashhur (u "The C Programming Language" kitobida keltirgan):

1011010 da 7 bit bor, lekin sikl 4 marta aylandi — faqat 1 lar uchun. Murakkablik: O(k), bu yerda k — 1 lar soni. 32 bitli sonda k ≤ 32, shuning uchun amalda bu O(1) — n ning kattaligiga bog'liq emas.

Maslahat: Yana bitta qo'shni hiyla: n & -n faqat eng o'ngdagi 1 ni qoldiradi: 6 & -6 = 2 (110 dan 010). Manfiy son ikkilik to'ldiruvchida "hamma bitni teskari qilib, 1 qo'shish" — shuning uchun eng o'ngdagi 1 gacha bitlar mos keladi. Bu Fenwick tree darsida kerak bo'ladi.

4. Son 2 ning darajasimi?

4.1 Bitta 1 — bitta ifoda

2 ning darajalari ikkilikda qanday ko'rinadi? 1 = 1, 2 = 10, 4 = 100, 64 = 1000000. Hammasida aynan bitta 1 bor. Demak, eng o'ngdagi 1 ni o'chirsak, nol qolishi kerak:

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

console.log(isPowerOfTwo(64)); // true
console.log(isPowerOfTwo(48)); // false
console.log(isPowerOfTwo(0)); // false

n > 0 sharti nima uchun? 0 da 1 umuman yo'q: 0 & -1 = 0 — tekshiruvdan o'tib ketardi. Manfiy sonlar ham 2 ning darajasi emas. Sodda yechim — n ni 2 ga bo'la-bo'la 1 ga yetishini tekshirish — O(log n) qadam. Bitli ifoda bitta qadamda javob beradi.

Endi o'zingiz hisoblang. 12 ikkilikda 1100, 11 esa 1011. Demak, 12 & 11 natijasi — noldan farqli, shuning uchun 12 2 ning darajasi emas.

4.2 Qayerda kerak?

Xotira murakkabligi darsidagi dinamik massiv sig'imni ikki baravar oshirardi: 1, 2, 4, 8 — hammasi 2 ning darajasi. Ko'p xesh jadvallar ham o'lchamini 2 ning darajasida ushlaydi. Unda "indeks = xesh % o'lcham" o'rniga tezroq "xesh & (o'lcham − 1)" ishlatiladi (Hash table ichidan). Rasm va video kodeklarida, xotira bloklarida ham shunday.

Tekshirib ko'ring: Nega isPowerOfTwo da (n & (n - 1)) qavsga olingan?

5. Bitmask bilan hamma to'plamlar

5.1 G'oya: son — to'plam

Set menyu masalasiga qaytamiz. 3 ta taom bor: osh, lag'mon, manti. Har taom to'plamda yo bor, yo yo'q — 2 × 2 × 2 = 8 ta to'plam. Bit bayroqlar darsida bitmask'ni ruxsatlar to'plami sifatida ishlatgan edik. Bu yerda ham shunday: 3 bitli son — taomlar to'plami. 0-bit — osh, 1-bit — lag'mon, 2-bit — manti.

Endi eng qiziq joyi: 0 dan 7 gacha sanasak, hamma 8 ta to'plamni bittadan ko'rib chiqamiz. Har mask uchun mask & (1 << i) — "i-taom to'plamdami?" savoli. Qaysi to'plam narxi aynan 63 ming so'm?

Jadvalda har qator — bitta mask. Bitlar o'ngdan chapga sanaladi: eng o'ngdagi (0-bit) — osh, o'rtadagi — lag'mon, chapdagi — manti. Shuning uchun ustunlar "manti, lag'mon, osh" tartibida. Masalan, 011 — lag'mon va osh. 1 << n — 2ⁿ (bitta 1 ni n o'ringa siljitish, Bitwise operatorlar darsidan). Rekursiya ham, qo'shimcha massiv ham kerak bo'lmadi.

5.2 Murakkablik va o'lchov

To'plamlar soni 2ⁿ, har birida n ta bit tekshiriladi — O(2ⁿ · n) vaqt. Bu eksponensial o'sish: har yangi taom ishni ikki baravardan ko'proq oshiradi. O'lchov (narxlar urug'li generatordan, byudjet 100):

Har qatorda n bittaga oshdi — vaqt ikki baravar. 20 taomda 0,1 soniya. Shu tezlikda 30 taomda taxminan 1 500 baravar ko'p ish — ikki daqiqadan oshadi. Shuning uchun bitmask usuli kichik n uchun (≈ 20–25 gacha) yaxshi. Kattaroq n da backtracking va kesish yoki dinamik dasturlash kerak bo'ladi.

5.3 32 bit chegarasi

JavaScript'da 1 << 31 manfiy son beradi, 1 << 32 esa 1 — siljitish 32 ga qoldiqli bo'linadi:

console.log(1 << 30); // 1073741824
console.log(1 << 31); // -2147483648
console.log(1 << 32); // 1

Demak, mask < 1 << n sharti n ≤ 30 da to'g'ri ishlaydi. n = 31 da 1 << 31 manfiy — sikl bir marta ham aylanmaydi. n = 32 da — faqat bitta to'plam. Xato xabari yo'q, natija jim buziladi. Amalda bu chegara muammo emas — 30 taomda 2³⁰ ≈ milliard to'plam, baribir juda sekin. Lekin funksiya kirishni tekshirib, aniq xato bersin (3-mashqda shunday qilamiz).

6. Chegaraviy holatlar

Bo'sh ro'yxat qatori muhim: XOR "topilmadi" va "chek raqami 0" ni farqlay olmaydi. Bunday holatda bo'sh ro'yxatni alohida tekshiring va null qaytaring.

7. Ko'p uchraydigan xatolar

7.1 Qavssiz bitli tekshiruv

console.log(8 & 8 - 1 === 0); // 0
console.log((8 & (8 - 1)) === 0); // true

Birinchi qatorda 8 — 2 ning darajasi, lekin javob 0 (yolg'on qiymat). Sabab — ustuvorlik: 8 - 1 === 0 avval hisoblanadi (false), keyin 8 & false = 0. Tuzatish: bitli amalni solishtirishdan oldin doim qavsga oling.

7.2 Katta sonlarda bitli amal

ID, telefon raqami, vaqt belgisi (Date.now()) — 32 bitdan katta. Ularda ^, &, | jim buziladi. Tuzatish: 2³¹ dan katta bo'lishi mumkin bo'lsa — BigInt yoki bitlarsiz yechim.

7.3 1 << n ni n ≥ 31 da ishlatish

1 << 31 manfiy, 1 << 32 = 1. Tuzatish: n ≤ 30 ni tekshiring; katta daraja kerak bo'lsa 2 ** n (oddiy son) yoki 1n << BigInt(n).

7.4 XOR'ni "toq marta" holatida ishlatish

Har raqam ikki martadan emas, uch martadan uchrasa — XOR noto'g'ri javob beradi. Tuzatish: shartni o'qing: XOR faqat "boshqalari juft marta" bo'lganda ishlaydi.

8. Mashqlar

1-mashq (oson): Qo'lda hisoblang

(a) 6 ^ 9 ^ 6 nechaga teng? Hisoblamasdan, xususiyatlar bilan javob bering. (b) countBits(13) da sikl necha marta aylanadi va har qadamda n qanday bo'ladi?

2-mashq (o'rta): Yo'qolgan chek

Kun davomida cheklar 1 dan n gacha raqamlangan. Kechqurun bittasi yo'qoldi — ro'yxatda n − 1 ta raqam bor. findMissing(receipts, n) funksiyasini XOR bilan yozing, O(1) xotirada. Ishora: 1..n ning hammasini va ro'yxatdagilarning hammasini bitta XOR zanjiriga qo'shing — nima juft bo'ladi?

function findMissing(receipts, n) {
  let acc = 0;
  for (let i = 1; i <= n; i++) acc ^= i; // bo'lishi kerak bo'lganlar
  for (const r of receipts) acc ^= r; // borlari
  return acc; // juftsiz qolgani — yo'qolgani
}

console.log(findMissing([3, 1, 5, 2], 5)); // 4
console.log(findMissing([], 1)); // 1

3-mashq (qiyin): Bitlar to'plami va testlar

kurs/mashqlar/14/14-bitlar/bitlar.test.mjs faylida to'rtta funksiya yozing va node:test bilan sinang:

1. findUnpaired(receipts) — XOR bilan.
2. countBits(n) — Kernighan usuli.
3. isPowerOfTwo(n) — butun bo'lmagan son uchun ham false (Number.isInteger).
4. combosForBudget(menu, budget) — menu — { name, price } lar massivi. Narxi aynan budget bo'lgan hamma to'plamlarni nomlar massivi sifatida qaytaradi. 30 tadan ko'p taomda RangeError tashlaydi.

Menyu: osh 35 000, lag'mon 28 000, manti 30 000, ko'k choy 5 000. Byudjet 63 000 da ikkita javob bor — qaysilar?

// kurs/mashqlar/14/14-bitlar/bitlar.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function findUnpaired(receipts) {
  let acc = 0;
  for (const r of receipts) acc ^= r;
  return acc;
}

function countBits(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;
    count++;
  }
  return count;
}

function isPowerOfTwo(n) {
  return Number.isInteger(n) && n > 0 && (n & (n - 1)) === 0;
}

function combosForBudget(menu, budget) {
  const n = menu.length;
  if (n > 30) throw new RangeError("30 tadan ko'p taom");
  const result = [];
  for (let mask = 0; mask < 1 << n; mask++) {
    let sum = 0;
    const names = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        sum += menu[i].price;
        names.push(menu[i].name);
      }
    }
    if (sum === budget) result.push(names);
  }
  return result;
}

test("juftsiz chek", () => {
  assert.equal(findUnpaired([104, 107, 104, 109, 107]), 109);
  assert.equal(findUnpaired([42]), 42);
});

test("bitlar soni", () => {
  assert.equal(countBits(0), 0);
  assert.equal(countBits(0b1011010), 4);
  assert.equal(countBits(255), 8);
});

test("2 ning darajasi", () => {
  for (const n of [1, 2, 64, 2 ** 30]) {
    assert.ok(isPowerOfTwo(n), n);
  }
  for (const n of [0, -8, 6, 100, 2.5]) {
    assert.ok(!isPowerOfTwo(n), n);
  }
});

test("byudjetga mos to'plamlar", () => {
  const menu = [
    { name: "osh", price: 35000 },
    { name: "lag'mon", price: 28000 },
    { name: "manti", price: 30000 },
    { name: "ko'k choy", price: 5000 },
  ];
  assert.deepEqual(combosForBudget(menu, 63000), [
    ["osh", "lag'mon"],
    ["lag'mon", "manti", "ko'k choy"],
  ]);
  assert.deepEqual(combosForBudget(menu, 0), [[]]); // bo'sh to'plam
  assert.deepEqual(combosForBudget(menu, 1000), []);
});

test("31 ta taom — xato", () => {
  const big = Array.from({ length: 31 }, (_, i) => ({
    name: `t${i}`,
    price: 1,
  }));
  assert.throws(() => combosForBudget(big, 5), RangeError);
});

✔ juftsiz chek (0.7256ms)
✔ bitlar soni (0.1382ms)
✔ 2 ning darajasi (0.1796ms)
✔ byudjetga mos to'plamlar (1.3614ms)
✔ 31 ta taom — xato (0.4704ms)
ℹ tests 5
ℹ suites 0
ℹ pass 5
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 86.9997

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md jadvaliga to'rt qator qo'shing: juftsiz chek (Map va XOR), bitlarni sanash, 2 ning darajasi va set menyu (bitmask). Har birida vaqt va xotira.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Juftsiz chek | Map bilan | O(n) | O(n) |
| Juftsiz chek | XOR | O(n) | O(1) |
| Bitlarni sanash | Kernighan | O(k), k ≤ 32 | O(1) |
| 2 ning darajasi | n & (n - 1) | O(1) | O(1) |
| Set menyu | bitmask | O(2ⁿ · n) | O(1) |

git add 14/MURAKKABLIK.md 14/14-bitlar
git commit -m "14/14: XOR, bitlarni sanash, bitmask to'plamlar"

9. Real ishda

• Ruxsatlar va sozlamalar. Linux fayl ruxsatlari, Discord va Telegram bot ruxsatlari, o'yinlardagi holat bayroqlari — bitmask. React ham ichkarida yangilanishlarning ustuvorligini bitmask bilan belgilaydi (React'ni kursda alohida o'rganamiz).
• Katta to'plamlar. "Bugun kim saytga kirdi?" degan savol uchun million foydalanuvchiga million bit — atigi 125 KB. Redis'dagi SETBIT va BITCOUNT buyruqlari aynan shunday ishlaydi.
• Protsessor darajasida. Zamonaviy protsessorlarda bitlarni sanash uchun alohida buyruq (POPCNT) bor. Shaxmat dasturlari taxtani 64 bitli sonlarda saqlaydi.
• Intervyu. "Single Number" (LeetCode 136), "Number of 1 Bits" (191), "Power of Two" (231), "Missing Number" (268), "Subsets" (78) — bitlar bo'yicha eng ko'p beriladigan savollar.

Xulosa

• XOR: x ^ x = 0, x ^ 0 = x, tartib ahamiyatsiz. Hammasini XOR qilsangiz — juftsiz qoladi. O(n) vaqt, O(1) xotira; 8 mln chekda Map dan ≈ 30 baravar tez.
• n & (n - 1) eng o'ngdagi 1 ni o'chiradi. Kernighan usuli 1 lar soni qadar aylanadi.
• n > 0 && (n & (n - 1)) === 0 — 2 ning darajasi. Qavslarni unutmang: === & dan oldin bajariladi.
• Bitmask: 0 dan 2ⁿ − 1 gacha sanash — hamma to'plamlar. O(2ⁿ · n): +1 element — vaqt ×2.
• Bitli amallar 32 bitda ishlaydi: katta son va 1 << 31 jim buziladi — BigInt yoki tekshiruv kerak.

Keyingi dars: Sonlar nazariyasi asoslari — EKUB va EKUK, tub sonlar, Eratosfen g'alviri, modul arifmetikasi va tez darajaga ko'tarish.

Manbalar

• Henry S. Warren, "Hacker's Delight", 2-nashr, Addison-Wesley, 2012 — 2-bob (eng o'ngdagi bit hiylalari), 5-bob (bitlarni sanash).
• Brian W. Kernighan, Dennis M. Ritchie, "The C Programming Language", 2-nashr, 1988 — 2-bob, 2-9-mashq (x &= (x - 1)).
• ECMAScript spetsifikatsiyasi: ToInt32, siljitish operatorlari (siljitish soni 32 ga qoldiq bilan) — tc39.es/ecma262
• Redis hujjatlari: SETBIT, BITCOUNT — redis.io/docs