Power of Two

Q: Bir sayının ikinin kuvveti olup olmadığını nasıl kontrol edersiniz?

n > 0 ve n & (n-1) 0'a eşit olduğunda true döndürün. İkinin kuvvetinin tam olarak bir tane 1 biti vardır ve 1 çıkarmak bu biti temizlerken yalnızca altındaki bitleri ayarlar; bu nedenle AND sonucu 0 olur. Bit işlemleri kullanmadan, n çift olduğu sürece yarıya bölün ve sonunda 1'e ulaştığınızı kontrol edin.

Q: İki Kuvveti algoritmasının zaman karmaşıklığı nedir?

n & (n-1) kontrolü O(1) zaman ve alan karmaşıklığında çalışır: bir karşılaştırma, bir çıkarma ve bir AND işlemi. Yarıya indirme döngüsü O(log n) zamanda çalışır; 32 bitlik bir tamsayı için en fazla 31 adım sürer.

Q: 1 ikinin kuvveti midir? 0 ikinin kuvveti midir?

1, ikinin kuvvetidir; çünkü 2^0 = 1 ve ikilik gösteriminde bir tane 1 biti vardır. 0 ise değildir: hiçbir tam sayı üs 0 sonucunu vermez ve 0'ın hiç 1 biti yoktur. Negatif sayılar da hiçbir zaman ikinin kuvveti değildir.

KolayBit işlemleri

+10

Bir tam sayı n alırsın. n bir ikinin kuvvetiyse, yani bir k ≥ 0 tam sayısı için n = 2^k ise true, aksi hâlde false döndür. Yani 1, 2, 4 ve 8 sayılır; 0, 6 ve tüm negatif sayılar sayılmaz.

Fonksiyon

isPowerOfTwo(n: integer) → boolean

ninteger: test edilecek tam sayı; sıfır veya negatif olabilir
Döndürürboolean: n, herhangi bir k ≥ 0 için 2^k'ye eşitse true, aksi takdirde false

Kısıtlar

-2³¹ ≤ n ≤ 2³¹-1

Örnekler

Girdi: n = 16
Çıktı: true
Açıklama: 16 = 2 × 2 × 2 × 2 = 2^4. İkilik sistemde 10000 şeklindedir; tek bir 1 biti vardır.

Girdi: n = 24
Çıktı: false
Açıklama: 24 = 8 × 3. İkiye bölünce 12, 6 ve ardından 3 elde edilir; bu tek sayıdır ama 1 değildir. İkilik sistemde 24, 11000 şeklindedir; iki adet 1 biti vardır.

Girdi: n = 1
Çıktı: true
Açıklama: 1 = 2^0, yani ikinin bir kuvvetidir. İkili biçimi 1 tam olarak bir tane 1 bitine sahiptir.

Gönderirken +17 gizli test

Ek soru

Bir döngü kullanmadan, aynı bit işlemleriyle n değerinin dördün kuvveti olup olmadığını test edebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

İkinin bir kuvveti, ikilik sistemde sabit bir şekle sahiptir: 10000 örneğinde olduğu gibi, ardından sıfırlar gelen bir 1 biti. n tek olana kadar ikiye bölerek bu şekli doğrulayabilirsiniz; bu işlem en fazla 31 adım sürer. Ya da en düşük 1 bitini temizleyen ve yalnızca bu bit tek bitsiyse 0 bırakan n & (n-1) işlemiyle bunu tek adımda doğrulayabilirsiniz. Her iki sürümde de önce işaret kontrolü yapılır; çünkü sıfır ve negatif sayılar, ilk bakışta bariz görünen kodu bozar.

Sayı çift olduğu sürece 2'ye böl

Sezgi

n = 2^k ise, onu tam olarak k kez 2'ye bölebilir ve 1'e ulaşabilirsin; bu süreçteki her değer çifttir. n değerinin 1'den büyük tek bir çarpanı varsa, yarıya bölme işlemi 1 olmayan tek bir sayıda durur. 16 için: 16, 8, 4, 2, 1; dolayısıyla yanıt true olur. 24 için: 24, 12, 6, 3 ve 3 tek ama 1 değil; dolayısıyla yanıt false olur.

Döngüden önce n ≤ 0 için false döndür. Hiçbir 2 kuvveti sıfır veya negatif değildir ve döngü 0'da asla sonlanmaz; çünkü 0 çifttir ve 0'ın yarısı yine 0'dır.

Her adımda n yarıya iner; bu nedenle 32 bitlik bir girdi en fazla 31 adım sürer: O(log n) zaman ve O(1) alan.

Algoritma

Eğer n ≤ 0 ise false döndür.
n çift olduğu sürece onu 2'ye böl.
n artık 1 mi, bunu döndür.

def isPowerOfTwo(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

n & (n-1) ile en düşük değerli biti temizleyin

Sezgi

İkilik sistemde ikinin bir kuvvetini yazdığınızda, ardından sıfırlar gelen tek bir 1 elde edersiniz: 16, 10000 şeklindedir. 1’den çıkarmak, o 1’i 0’a ve altındaki her 0’ı 1’e dönüştürür: 15, 01111 şeklindedir. İki sayıda ortak 1 biti yoktur, bu nedenle 16 & 15 0’dır.

Diğer tüm pozitif sayılarda en az iki 1 biti bulunur. 1’den çıkarmak yalnızca en düşük 1 bitini ve altındaki sıfırları değiştirir; bu nedenle daha yüksek konumdaki her 1 biti iki sayıda da bulunur ve AND sonucu 0 olmaz. 11000 olan 24 için 23 = 10111 elde edersiniz ve 24 & 23, 16 olan 10000 değeridir.

Önce n > 0 koşulunu kontrol edin. 0 & -1 sonucu 0’dır ve 32 bitlik aritmetikte -2^31, ardından 31 sıfır gelen tek bir 1 bitidir; bu nedenle yalnızca AND işlemi her ikisini de ikinin kuvveti olarak değerlendirebilir. Testin tamamı bir karşılaştırma, bir çıkarma ve bir AND işleminden oluşur: zaman ve alan karmaşıklığı O(1). Lua 5.1’de AND operatörü bulunmadığından Lua kodu AND işlemini her seferinde bir bit olacak şekilde, 32 bitlik bir n için en fazla 31 adımda oluşturur; test aynıdır.

Algoritma

Eğer n ≤ 0 ise false döndür.
n & (n-1) ifadesini hesapla; bu, en düşük 1 biti temizlenmiş n değeridir.
Sonucun 0 olup olmadığını döndür.

def isPowerOfTwo(n):
    # One set bit: n - 1 flips it and every bit below, so the AND is 0.
    return n > 0 and n & (n - 1) == 0

Tuzaklar ve uç durumlar

Bit testi tek satırdır ve hataların çoğu, bu testin kullanılmak üzere tasarlanmadığı girdilerle ilgilidir.

İşaret kontrolünü atlamak. 0 & (0-1) sonucu 0'dır, bu nedenle 0 AND testini geçer. 32 bitlik tamsayılarda -2^31 de geçer, çünkü ikili gösterimi tek bir 1 bitinden oluşur. Her ikisi de false döndürmelidir.
Yarıya indirme döngüsünü 0 üzerinde çalıştırmak. Sıfır çifttir ve yarıya indirilince yine 0 olur; dolayısıyla döngü hiç bitmez.
Parantezleri kaldırmak. ==, & işleminden daha yüksek önceliğe sahiptir; bu nedenle C, C++ ve JavaScript'te n & n - 1 == 0, n & ((n - 1) == 0) şeklinde okunur ve hata vermeden yanlış sonuç verir; Java ve C# ise bunu tür hatası olarak reddeder. (n & (n - 1)) == 0 yazın.
Logaritma kullanmak. Çift duyarlıkta log(536870912) / log(2) sonucu 29 yerine 29.000000000000004 olur; bu nedenle tam sayı kontrolü 2^29 için false döndürür.

Sıkça sorulan sorular4

Bir sayının ikinin kuvveti olup olmadığını nasıl kontrol edersiniz?

n > 0 ve n & (n-1) 0'a eşit olduğunda true döndürün. İkinin kuvvetinin tam olarak bir tane 1 biti vardır ve 1 çıkarmak bu biti temizlerken yalnızca altındaki bitleri ayarlar; bu nedenle AND sonucu 0 olur. Bit işlemleri kullanmadan, n çift olduğu sürece yarıya bölün ve sonunda 1'e ulaştığınızı kontrol edin.

n & (n-1) en düşük ayarlı biti neden temizler?

1 çıkarmak, en düşük 1 bitinden ödünç alır: bu bit 0 olur ve altındaki her 0, 1 olur; daha yüksek bitler ise aynı kalır. Özgün değerle AND işlemi yapmak, yalnızca her ikisinde de 1 olan bitleri korur; bunlar da tam olarak daha yüksek bitlerdir. İki kuvveti olan bir sayıda daha yüksek bit olmadığından sonuç 0 olur.

İki Kuvveti algoritmasının zaman karmaşıklığı nedir?

n & (n-1) kontrolü O(1) zaman ve alan karmaşıklığında çalışır: bir karşılaştırma, bir çıkarma ve bir AND işlemi. Yarıya indirme döngüsü O(log n) zamanda çalışır; 32 bitlik bir tamsayı için en fazla 31 adım sürer.

1 ikinin kuvveti midir? 0 ikinin kuvveti midir?

1, ikinin kuvvetidir; çünkü 2^0 = 1 ve ikilik gösteriminde bir tane 1 biti vardır. 0 ise değildir: hiçbir tam sayı üs 0 sonucunu vermez ve 0'ın hiç 1 biti yoktur. Negatif sayılar da hiçbir zaman ikinin kuvveti değildir.

Python

def isPowerOfTwo(n):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

n = 16

Beklenen

true