Tarkibga o'tish

1 bo'lgan bitlar soni

Ishorasiz 32-bitli butun son n berilgan. Uning ikkilik ko'rinishida nechta 1 bit borligini toping. Bu amal Hamming weight yoki popcount deb ataladi.

Kirish:  n = 11  (ikkilik: 0000 1011)
Chiqish: 3        // uchta 1 bit bor: birinchi, ikkinchi, to'rtinchi

Kirish:  n = 128  (ikkilik: 1000 0000)
Chiqish: 1

Kirish:  n = 2147483645  (ikkilik: 0111 1111 1111 1111 1111 1111 1111 1101)
Chiqish: 30

Birinchi yondashuv: bitlarni bir-bir tekshirish

n ning har bitini & 1 bilan tekshirib, keyin o'ngga siljitib, n = 0 bo'lgunicha davom etish:

FUNCTION COUNT_BITS_SHIFT(n)
    count = 0
    WHILE n > 0
        count = count + (n & 1)   // oxirgi bit 1 mi?
        n     = n >> 1             // o'ngga siljitish
    RETURN count

n & 1 — eng quyi bitni ajratib oladi. n >> 1 — barcha bitlarni bir pozitsiya o'ngga siljitadi, eng quyi bit yo'qoladi.

Dry run: n = 11 = 1011₂

n = 1011,  n & 1 = 1, count = 1,  n >> 1 = 0101
n = 0101,  n & 1 = 1, count = 2,  n >> 1 = 0010
n = 0010,  n & 1 = 0, count = 2,  n >> 1 = 0001
n = 0001,  n & 1 = 1, count = 3,  n >> 1 = 0000
n = 0 → to'xtash

RETURN 3

Murakkablik: O(32) = O(1) — 32-bitli sonda maksimum 32 iteratsiya.

Note

Ishorali sonda arifmetik o'ng siljitish (>>) salbiy son uchun chapdan 1 qo'shadi va tsikl chiqmaydi. Ishorasiz sonda yoki >>> 1 (mantiqiy siljitish) ishlatish kerak. Masalada son ishorasiz deb berilgan.

Ikkinchi yondashuv: Brian Kernighan algoritmi

Har operatsiyada eng quyi 1 bitni o'chirish:

n & (n - 1)   // eng quyi 1 bitni o'chiradi

Nima uchun? n - 1 operatsiyasi eng quyi 1 bitni 0 ga, undan pastdagi barcha 0 bitlarni 1 ga aylantiradi. n & (n - 1) esa faqat shu eng quyi 1 bitni o'chiradi:

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

FUNCTION COUNT_BITS_KERNIGHAN(n)
    count = 0
    WHILE n > 0
        n     = n & (n - 1)   // eng quyi 1 bitni o'chirish
        count = count + 1
    RETURN count

Dry run: n = 11 = 1011₂

Qadam 1: n = 1011
  n & (n-1) = 1011 & 1010 = 1010
  count = 1

Qadam 2: n = 1010
  n & (n-1) = 1010 & 1001 = 1000
  count = 2

Qadam 3: n = 1000
  n & (n-1) = 1000 & 0111 = 0000
  count = 3

n = 0 → to'xtash
RETURN 3

Murakkablik: O(k) — k ta 1 bit soni. 1 bit kam bo'lsa birinchi yondashuvdan tezroq.

Yondashuvlar taqqoslanishi

Yondashuv Iteratsiyalar G'oya
Siljitish 32 (har doim) Har bitni tekshirish
Kernighan k (1 bitlar soni) Har operatsiyada bitta 1 bit o'chirish

n = 1000 0000 (128) uchun: - Siljitish: 32 ta iteratsiya - Kernighan: 1 ta iteratsiya

n = 1111 1111 (255) uchun: - Siljitish: 32 ta iteratsiya - Kernighan: 8 ta iteratsiya

32-bitli son uchun ikkalasi ham O(1), lekin Kernighan 1 bit kam bo'lganda amalda tezroq.

Edge case'lar

n = 0: 1 bit yo'q → 0. Ikkala tsikl ham boshlanmaydi.

n = 1: bitta 1 bit → 1.

n = 0xFFFFFFFF (barcha 32 bit 1): 32 ta 1 bit → 32.

Salbiy son (ishorali kontekstda): masala ishorasiz son uchun. Ishorali kontekstda n = -1 = 1111...1 — barcha 32 bit 1.

Xulosa

1 bo'lgan bitlar soni ikkita asosiy usulda hisoblanadi. Siljitish usuli — har bitni ketma-ket tekshiradi, 32 iteratsiya. Brian Kernighan algoritmi — n & (n-1) bilan har safar bitta 1 bitni o'chiradi, k iteratsiya (k — 1 bitlar soni).

Ikkalasi ham 32-bitli sonda O(1). Kernighan 1 bit soni kam bo'lganda amalda tezroq.