rust_algorithms/numbers/
bits.rs

1//! Bit bilan ishlash (bit manipulation) — kichik, lekin kuchli hiylalar.
2//!
3//! Bitlar bilan ishlash ko'p algoritmlarni sekundlar o'rniga millisekundlarda
4//! bajarishga imkon beradi: to'plamlarni `u64` da saqlash, DP bitmask, hash va h.k.
5
6/// Sonda nechta 1 biti bor (population count) — Brian Kernighan usuli.
7///
8/// **G'oya:** `n & (n - 1)` amali eng past 1 bitni o'chiradi. Demak, tsikl
9/// nechta 1 bit bo'lsa, shuncha marta aylanadi (32/64 marta emas!).
10///
11/// - **Time:** O(bitlar soni), amalda `u64::count_ones()` protsessor buyrug'i.
12///
13/// # Misol
14/// ```
15/// use rust_algorithms::numbers::count_ones;
16///
17/// assert_eq!(count_ones(0b1011), 3);
18/// assert_eq!(count_ones(0), 0);
19/// ```
20pub fn count_ones(mut n: u64) -> u32 {
21    let mut c = 0;
22    while n != 0 {
23        n &= n - 1; // eng past 1 bitni o'chiradi
24        c += 1;
25    }
26    c
27}
28
29/// `n` ikkining darajasimi? (1, 2, 4, 8, …)
30///
31/// **G'oya:** ikkining darajasida faqat bitta 1 bit bor, shuning uchun
32/// `n & (n - 1) == 0`.
33///
34/// # Misol
35/// ```
36/// use rust_algorithms::numbers::is_power_of_two;
37///
38/// assert!(is_power_of_two(64));
39/// assert!(!is_power_of_two(0));
40/// assert!(!is_power_of_two(48));
41/// ```
42pub fn is_power_of_two(n: u64) -> bool {
43    n != 0 && (n & (n - 1)) == 0
44}
45
46/// Eng past 1 bitni ajratib oladi: `n & (-n)`.
47///
48/// Fenwick tree (BIT) ma'lumot strukturasining asosi.
49///
50/// # Misol
51/// ```
52/// use rust_algorithms::numbers::lowest_set_bit;
53///
54/// assert_eq!(lowest_set_bit(12), 4); // 1100 → 0100
55/// assert_eq!(lowest_set_bit(0), 0);
56/// ```
57pub fn lowest_set_bit(n: u64) -> u64 {
58    n & n.wrapping_neg()
59}
60
61/// Uchinchi o'zgaruvchisiz almashtirish (XOR swap) — klassik hiyla.
62///
63/// > Amalda `std::mem::swap` dan foydalaning: u tezroq va o'qilishi oson.
64/// > Bu funksiya XOR ning xossasini ko'rsatish uchun: `a ^ a = 0`, `a ^ 0 = a`.
65///
66/// # Misol
67/// ```
68/// use rust_algorithms::numbers::swap_xor;
69///
70/// assert_eq!(swap_xor(3, 5), (5, 3));
71/// ```
72#[allow(clippy::manual_swap)] // aynan XOR hiylasini ko'rsatish maqsadida
73pub fn swap_xor(a: u64, b: u64) -> (u64, u64) {
74    let (mut a, mut b) = (a, b);
75    a ^= b;
76    b ^= a;
77    a ^= b;
78    (a, b)
79}
80
81/// Bitmaskning **barcha qism to'plamlari** (o'zi va bo'sh to'plam bilan birga).
82///
83/// **G'oya:** `sub = (sub - 1) & mask` sehri maskning barcha qism to'plamlarini
84/// kamayish tartibida beradi. Bitmask DP da ("kommivoyajyor", "to'plamlarga bo'lish")
85/// asosiy vosita.
86///
87/// - **Time:** O(2^(maskdagi 1 bitlar soni)).
88///
89/// # Misol
90/// ```
91/// use rust_algorithms::numbers::subsets_of_mask;
92///
93/// let mut s = subsets_of_mask(0b101);
94/// s.sort();
95/// assert_eq!(s, vec![0b000, 0b001, 0b100, 0b101]);
96/// ```
97pub fn subsets_of_mask(mask: u32) -> Vec<u32> {
98    let mut out = Vec::new();
99    let mut sub = mask;
100    loop {
101        out.push(sub);
102        if sub == 0 {
103            break;
104        }
105        sub = (sub - 1) & mask;
106    }
107    out
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113
114    #[test]
115    fn count_ones_std_bilan_mos() {
116        for n in 0u64..10_000 {
117            assert_eq!(count_ones(n), n.count_ones());
118        }
119        assert_eq!(count_ones(u64::MAX), 64);
120    }
121
122    #[test]
123    fn ikkining_darajalari() {
124        for k in 0..63 {
125            assert!(is_power_of_two(1u64 << k));
126        }
127        for n in [0u64, 3, 5, 6, 7, 100] {
128            assert!(!is_power_of_two(n));
129        }
130    }
131
132    #[test]
133    fn eng_past_bit() {
134        assert_eq!(lowest_set_bit(1), 1);
135        assert_eq!(lowest_set_bit(0b1010_0000), 0b10_0000);
136    }
137
138    #[test]
139    fn xor_swap() {
140        for a in 0u64..20 {
141            for b in 0u64..20 {
142                assert_eq!(swap_xor(a, b), (b, a));
143            }
144        }
145    }
146
147    #[test]
148    fn qism_toplamlar_soni_togri() {
149        for mask in 0u32..64 {
150            let s = subsets_of_mask(mask);
151            assert_eq!(s.len(), 1 << mask.count_ones());
152            assert!(s.iter().all(|&x| x & mask == x)); // har biri mask ichida
153        }
154    }
155}
rust_algorithms/numbers/bits.rs

rust_algorithms/numbers/
bits.rs
