Tarkibga o'tish

Son 4 ning darajasimi?

Butun son n berilgan. U 4 ning darajasi ekanligini aniqlang.

4 ning darajalari: 1, 4, 16, 64, 256, 1024, ... (ya'ni 4^0, 4^1, 4^2, 4^3, ...).

Kirish: n = 16
Chiqish: TRUE   // 4^2

Kirish: n = 5
Chiqish: FALSE

Kirish: n = 1
Chiqish: TRUE   // 4^0 = 1

Kirish: n = 0
Chiqish: FALSE

Kirish: n = -4
Chiqish: FALSE

Avval: 2 ning darajasi qanday tekshiriladi?

4 ning darajasi — 2 ning darajasining maxsus holati. Shuning uchun 2 ning darajasini tekshirishdan boshlaymiz.

2 ning darajasi (1, 2, 4, 8, 16, ...) ikkilik ko'rinishida bitta 1 bitga ega:

1  = 0000 0001
2  = 0000 0010
4  = 0000 0100
8  = 0000 1000
16 = 0001 0000

Tekshirish: n > 0 va n & (n - 1) = 0.

n     = 1000
n - 1 = 0111
n & (n-1) = 0000 = 0 → 2 ning darajasi ✓

Shu shartni qo'llaganda 4 ning darajalari ham qamrab olinadi — lekin 8, 32 kabi boshqa 2 ning darajalari ham o'tib ketadi. Qo'shimcha shart kerak.

4 ning darajalari ikkilikda

4^0 = 1   = 0000 0001   // 1-chi pozitsiya (0-indexed: 0)
4^1 = 4   = 0000 0100   // 3-chi pozitsiya
4^2 = 16  = 0001 0000   // 5-chi pozitsiya
4^3 = 64  = 0100 0000   // 7-chi pozitsiya
4^4 = 256 = 0001 0000 0000  // 9-chi pozitsiya

Ko'rinadiki, 4 ning darajalari ikkilikda faqat juft pozitsiyalarda 1 bitga ega (0-indexed: 0, 2, 4, 6, ...).

Birinchi yondashuv: ketma-ket bo'lish

FUNCTION IS_POWER_OF_FOUR_NAIVE(n)
    IF n ≤ 0
        RETURN FALSE
    WHILE n % 4 = 0
        n = n / 4
    RETURN n = 1

n ni 4 ga bo'lish mumkin bo'lgunicha bo'lib, oxirida 1 qolsa — 4 ning darajasi.

Murakkablik: O(log₄ n).

Ikkinchi yondashuv: bit manipulyatsiya + maska

Ikki shart birlashtiriladi:

  1. 2 ning darajasi: n > 0 va n & (n - 1) = 0
  2. 1 bit juft pozitsiyada: n & 0x55555555 ≠ 0

0x55555555 — hex ko'rinishdagi maska:

0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101₂

Bu maskaning juft pozitsiyalardagi (0, 2, 4, ...) bitlari 1. Agar n ning 1 biti juft pozitsiyada bo'lsa, n & 0x55555555 ≠ 0.

FUNCTION IS_POWER_OF_FOUR_BITMASK(n)
    RETURN n > 0
       AND (n & (n - 1)) = 0
       AND (n & 0x55555555) ≠ 0

Tekshirish:

n = 16 = 0001 0000

n > 0? ✓

n & (n-1) = 0001 0000 & 0000 1111 = 0000 0000 = 0 ✓ (2 ning darajasi)

n & 0x55555555:
  0001 0000
& 0101 0101 0101 0101 0101 0101 0101 0101
=  0001 0000 ≠ 0 ✓ (4-pozitsiya juft: 0-indexed 4)

RETURN TRUE ✓

n = 8 = 0000 1000

n > 0? ✓
n & (n-1) = 0 ✓ (2 ning darajasi)
n & 0x55555555:
  0000 1000
& 0101 0101 ...
= 0000 0000 = 0 ✗ (3-pozitsiya toq)

RETURN FALSE ✓

Murakkablik: O(1).

Uchinchi yondashuv: modulo bilan

4 ning darajasi (4^k - 1) mod 3 = 0 va 2 ning darajasi hamdir. Boshqacha qilib: n mod 3 = 1 (4 ning darajasi uchun) va n & (n-1) = 0:

4^0 = 1   →  1 mod 3 = 1
4^1 = 4   →  4 mod 3 = 1
4^2 = 16  →  16 mod 3 = 1
4^3 = 64  →  64 mod 3 = 1

Nima uchun? 4 = 3 + 1, shuning uchun 4^k = (3+1)^k. Binomial teorema bo'yicha, 3ga bo'linganda barcha 3li qo'shiluvchilar tushib ketadi, faqat 1^k = 1 qoladi. Demak 4^k mod 3 = 1.

2 ning darajasi, lekin 4 ning darajasi emaslari: 2, 8, 32, 128... — bularning moduli:

2  mod 3 = 2
8  mod 3 = 2
32 mod 3 = 2

FUNCTION IS_POWER_OF_FOUR_MODULO(n)
    RETURN n > 0
       AND (n & (n - 1)) = 0
       AND n % 3 = 1

Murakkablik: O(1).

Yondashuvlar taqqoslanishi

Yondashuv Vaqt G'oya
Ketma-ket bo'lish O(log₄ n) 4 ga bo'ling
Bitmask O(1) 2 ning darajasi + juft pozitsiya
Modulo O(1) 2 ning darajasi + n % 3 = 1

Amalda uchala yondashuv ham 32-bitli son uchun O(1). Bitmask 0x55555555 va modulo % 3 — ikkalasi ham keng qo'llaniladigan usullar.

Edge case'lar

n = 0: 0 hech qanday darajaning natijasi emas → FALSE.

n = 1: 4^0 = 1 → TRUE. 1 & 0 = 0 ✓, 1 & 0x55... = 1 ≠ 0 ✓.

n < 0: Salbiy son 4 ning darajasi bo'lolmaydi → FALSE.

n = 2: 2 ning darajasi, lekin 4 ning emas. Bitmask tekshiruvi FALSE beradi: 2 = 0010, 1-pozitsiya toq.

n = INT_MAX = 2^31 - 1: n & (n - 1) ≠ 0 → FALSE.

Xulosa

4 ning darajasi — 2 ning darajasining bitta 1 biti faqat juft pozitsiyada (0, 2, 4, ...) turadi. Tekshirish:

  1. n > 0
  2. n & (n - 1) = 0 — bitta 1 bit (2 ning darajasi)
  3. n & 0x55555555 ≠ 0 — shu bit juft pozitsiyada

Yoki modulo: n > 0, n & (n-1) = 0, n % 3 = 1.

Har ikkalasi ham O(1) — 32-bitli son uchun doimiy miqdorda operatsiya.