17-bo'lim: Bit operatsiyalari

_{↑ Mundarijaga qaytish}

🔢 Bit darajasidagi amallar — tez (O(1)) va xotira-tejamkor. Tillar farqi: JS bit amallari 32-bitli ishorali butun songa aylantiriladi (kattaroq sonlar uchun BigInt), PHP ints — 64-bit, Python ints — cheksiz aniqlikda. Belgilar: & (AND), | (OR), ^ (XOR), ~ (NOT), <</>> (siljish).

183. Juft/toq — bit bilan

⏱ O(1) Oxirgi bit 0 bo'lsa juft. n % 2 dan tezroq (garchi zamonaviy kompilyatorlar farqni tekislasa ham).

JS

const isEven = n => (n & 1) === 0;

PHP

function isEven($n) {
    return ($n & 1) === 0;
}

Python

def is_even(n):
    return n & 1 == 0

184. k-bitni olish (get bit)

⏱ O(1) — o'ngdan 0-indeksli; 0 yoki 1 qaytaradi.

JS

const getBit = (n, k) => (n >> k) & 1;

PHP

function getBit($n, $k) {
    return ($n >> $k) & 1;
}

Python

def get_bit(n, k):
    return (n >> k) & 1

185. k-bitni o'rnatish (set bit → 1)

⏱ O(1)

JS

const setBit = (n, k) => n | (1 << k);

PHP

function setBit($n, $k) {
    return $n | (1 << $k);
}

Python

def set_bit(n, k):
    return n | (1 << k)

186. k-bitni tozalash (clear bit → 0)

⏱ O(1)

JS

const clearBit = (n, k) => n & ~(1 << k);

PHP

function clearBit($n, $k) {
    return $n & ~(1 << $k);
}

Python

def clear_bit(n, k):
    return n & ~(1 << k)

187. k-bitni almashtirish (toggle bit)

⏱ O(1)

JS

const toggleBit = (n, k) => n ^ (1 << k);

PHP

function toggleBit($n, $k) {
    return $n ^ (1 << $k);
}

Python

def toggle_bit(n, k):
    return n ^ (1 << k)

Yuqoridagi to'rt amal bitta umumiy g'oyaga asoslanadi — niqob (1 << k) faqat k-bitni ajratadi, so'ng OR/AND/XOR uni boshqaradi:

188. 2 ning darajasimi (power of two)

⏱ O(1) 2 ning darajasi ikkilik shaklda faqat bitta 1 bit (mas. 1000); n−1 esa pastki barcha bitlarni 1 qiladi (0111) → AND = 0.

JS

const isPowerOfTwo = n => n > 0 && (n & (n - 1)) === 0;

PHP

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

Python

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

189. O'rnatilgan bitlar soni (Brian Kernighan)

⏱ O(o'rnatilgan bitlar soni) · 💾 O(1) n &= n − 1 har safar eng past 1 bitni o'chiradi — sikl 32 emas, bitlar soniga teng aylanadi. Pythonda bin(n).count("1") ham bor.

JS

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

PHP

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

Python

def count_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

190. Eng past o'rnatilgan bitni ajratish (n & −n)

⏱ O(1) Ikkitalik to'ldiruvchi (two's complement) tufayli −n eng past 1 bitdan boshqa hammasini teskari qiladi; AND faqat o'sha bitni qoldiradi (12 = 1100 → 4 = 0100). Fenwick tree (BIT) da ishlatiladi.

JS

const lowestBit = n => n & -n;

PHP

function lowestBit($n) {
    return $n & -$n;
}

Python

def lowest_bit(n):
    return n & -n

191. XOR bilan swap (temp'siz)

⏱ O(1) a ^ b ^ b = a xossasiga asoslangan. Amaliyotda o'qilishi uchun oddiy almashtirish (a, b = b, a) afzal — bu shunchaki bit mantiqiga misol.

JS

a ^= b;
b ^= a;
a ^= b;

PHP

$a ^= $b;
$b ^= $a;
$a ^= $b;

Python

a ^= b
b ^= a
a ^= b

192. Yagona sonni topish (single number)

⏱ O(n) · 💾 O(1) Hamma element ikki marta, faqat bittasi bir marta. x^x=0, x^0=x — juftlar o'zaro yo'qoladi, yagona qoladi.

JS

const singleNumber = nums => nums.reduce((acc, x) => acc ^ x, 0);

PHP

function singleNumber($nums) {
    $acc = 0;
    foreach ($nums as $x) $acc ^= $x;
    return $acc;
}

Python

from functools import reduce
import operator

def single_number(nums):
    return reduce(operator.xor, nums, 0)

193. Bitlarni teskari ag'darish (32-bit)

⏱ O(1) (32 iteratsiya) JS'da >>> ishorasiz siljish, >>> 0 esa natijani ishorasiz 32-bit qiladi (JS bit amallari 32-bit ishorali bilan ishlaydi). PHP/Python butun sonlari kengroq.

JS

const reverseBits = n => {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;
  }
  return result >>> 0;
};

PHP

function reverseBits($n) {
    $result = 0;
    for ($i = 0; $i < 32; $i++) {
        $result = ($result << 1) | ($n & 1);
        $n >>= 1;
    }
    return $result;
}

Python

def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

---