Number of 1 Bits

Q: Number of 1 Bits işleminin zaman karmaşıklığı nedir?

Kaydırma döngüsü her ikili basamak için bir kez çalışır: O(log n) , burada en fazla 31 adım. n & (n-1) döngüsü her 1 biti için bir kez çalışır: O(k) ; burada k yanıttır. Her ikisi de O(1) ek alan kullanır.

KolayBit işlemleri

+10

Negatif olmayan bir tam sayı n veriliyor. n sayısını ikili biçimde yazın ve kaç basamağının 1 olduğunu döndürün. Bu sayı, ayarlanmış bit sayısı, nüfus sayımı veya Hamming ağırlığı olarak da adlandırılır. Örneğin, 6 ikili biçimde 110 şeklindedir, dolayısıyla iki adet 1 biti vardır.

Fonksiyon

hammingWeight(n: integer) → integer

ninteger: işaretli 32 bitlik bir int'e sığan negatif olmayan bir tam sayı
Döndürürinteger: n'nin ikili gösterimindeki 1 rakamlarının sayısı

Kısıtlar

0 ≤ n ≤ 2³¹-1

Örnekler

Girdi: n = 11
Çıktı: 3
Açıklama: 11, ikilik sistemde 1011 şeklindedir; bu da 8 + 2 + 1 eder. Dört ikilik basamağından üçü 1 olduğuna göre cevap 3'tür.

Girdi: n = 128
Çıktı: 1
Açıklama: 128, 2^7'dir ve 10000000 şeklinde yazılır: ardından sıfırlar gelen tek bir 1, yani cevap 1.

Ek soru

Bu işlev milyonlarca kez çalışsaydı, önceden hesaplanmış 256 sayımın bulunduğu bir tabloda dört arama yaparak 32 bitlik bir sayının bitlerini nasıl sayabilirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir dize oluşturmadan n sayısının ikilik basamaklarını inceleyin. Son biti okuyup kaydırarak kaldırmak, ikilik basamak başına bir adım gerektirir; en fazla 31 adım. En düşük 1 bitini n & (n-1) ile temizlemek ise her 1 biti için bir adım gerektirir; yani yanıt kadar adım.

Son biti kontrol et ve sağa kaydır.

Sezgi

n & 1, n sayısının son ikili basamağıdır: n tek olduğunda 1, çift olduğunda 0. Bunu sayaca ekleyin. Ardından n >> 1 bu basamağı atar ve sonraki basamağı son sıraya taşır; negatif olmayan bir sayı için bu, 2’ye bölüp aşağı yuvarlamaktır. 11, yani 1011 için n 0’a küçülürken son bitler 1, 1, 0 ve 1 olarak okunur: üç tane 1 biti.

Döngü n 0 olduğunda durur, bu nedenle baştaki sıfırları hiç ziyaret etmez: yaklaşık log2(n) adım; 128 için 8, en fazla 31 adım. Yalnızca n değerini ve sayacı saklar.

Algoritma

Sayacı 0'dan başlat.
n 0'dan büyük olduğu sürece n & 1 değerini sayaca ekle.
n değerini bir bit sağa kaydır.
n 0'a ulaştığında sayacı döndür.

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

En düşük ayarlı biti n & (n-1) ile temizle

Sezgi

1 çıkarmak, en düşük 1 bitini 0'a ve onun altındaki her 0 bitini 1'e dönüştürür; üstündeki bitleri ise değiştirmez. Bu nedenle n & (n-1) üst bitleri korur ve en düşük 1 bitini temizler: 12, 1100; 11, 1011 ve 1100 & 1011, 1000 değeridir.

Her adım tam olarak bir 1 bitini kaldırır; bu nedenle n değerinin 0 olması için gereken adım sayısı yanıttır. 128, 8 adım yerine 1 adımda tamamlanır; ancak 2^31-1 yine de 31 adım sürer. Lua 5.1'de bit işleçleri yoktur; bu nedenle onun sürümü, en düşük 1 bitini ikiye bölerek bulur ve onu çıkarır. Döngü yine her 1 biti için bir kez çalışır.

Algoritma

Sayacı 0'dan başlat.
n 0 olmadığı sürece, n değerini n & (n-1) ile değiştir.
Her değiştirmeden sonra sayaca 1 ekle.
Sayacı döndür.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

Tuzaklar ve uç durumlar

n > 1 koşuluyla döngüye girmek. Döngü, son 1 bitinden önce durur ve n = 1 için 0 döndürür.
Kayan noktalı sayı ile bölme yapmak. JavaScript, Lua ve R'de 11 / 2 sonucu 5.5'tir ve sonraki kalanlar kesirli olur. Math.floor, math.floor veya %/% ile aşağı yuvarlayın ya da bunun yerine kaydırma işlemi kullanın.
Lua 5.1'de n & 1 yazmak. Bit operatörleri olmadığından kod derlenmez; n % 2 ve math.floor(n / 2) kullanın.

Sıkça sorulan sorular3

Number of 1 Bits işleminin zaman karmaşıklığı nedir?

Kaydırma döngüsü her ikili basamak için bir kez çalışır: O(log n), burada en fazla 31 adım. n & (n-1) döngüsü her 1 biti için bir kez çalışır: O(k); burada k yanıttır. Her ikisi de O(1) ek alan kullanır.

Ayarlanmış bitleri sayan yerleşik bir fonksiyon var mı?

Çoğu dilde, genellikle tek bir işlemci komutuyla desteklenen bir tanesi bulunur: Java'da Integer.bitCount, GCC'de __builtin_popcount, Go'da bits.OnesCount, Rust'ta count_ones ve Python 3.10 ve sonraki sürümlerde int.bit_count. Bir mülakatta döngüyü yazın ve yerleşik işlevden bahsedin.

Hamming ağırlığı ile Hamming uzaklığı arasındaki fark nedir?

Bir sayının Hamming ağırlığı, ikili gösterimindeki 1’lerin sayısıdır; bu problem de bunu döndürür. İki sayı arasındaki Hamming uzaklığı, farklı oldukları bit konumlarının sayısıdır: a ^ b içindeki 1 bitleri sayın; çünkü XOR, yalnızca farklı oldukları konumları ayarlar.

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

Test #1

Test #2

Test #3

Argüman

n = 11

Beklenen Çıktı