Bitleri ve En Düşük Ayarlı Biti Sayma
popcount ve n & -n hilesini kullanın.
Bitleri ve En Düşük Ayarlı Biti Sayma, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
Birleri Sayma
Birçok problem, bir sayıda kaç bitin 1 olduğunu, yani sayının 1 bitlerinin sayısını sorar. Bu kavram alt kümelerin boyutlarında, tek-çiftlik kontrollerinde ve puanlamada karşınıza çıkar. 🔢
Python'un Yerleşik Sayma İşlemi
1 yapılmış bitleri saymanın en hızlı yolu, tamsayıların bit_count() yöntemidir. Döngü yok, uğraş yok; yalnızca birlerin sayısı.
print((13).bit_count()) # 0b1101 has 3 onesİkili Gösterim ve Sayma ile Sayın
bit_count yöntemini unutursanız sayıyı ikili metne dönüştürüp birleri sayabilirsiniz. Bu yöntem daha yavaştır; ancak anlaşılır ve hatırlaması kolaydır.
print(bin(13).count('1')) # 3En Düşük Konumdaki 1 Biti
En düşük konumdaki 1 biti, bir sayının en sağındaki 1'dir. Bu biti ayırmak, ileride Fenwick ağaçları ve alt küme yöntemleri için önemli bir adımdır.
n ve -n ile Ayırın
Ünlü n & -n yöntemi yalnızca en düşük konumdaki 1 bitini korur. İkili tümleyen gösterimindeki negatif sayılar bu yöntemin sihir gibi çalışmasını sağlar.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100n ve -n Neden Çalışır
Negatifini almak tüm bitleri tersine çevirip 1 ekler; böylece en düşük konumdaki 1'in altındaki her şey terslenir. AND işlemi yalnızca o tek biti bırakır.
En Düşük Konumdaki 1 Bitini Kaldırın
1 çıkarmak, sondaki sıfırlar boyunca ödünç alma işlemi yapar; bu nedenle n & (n - 1), en düşük konumdaki 1 bitini siler. Birleri teker teker kaldırmak için bu işlemi tekrarlayın.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Brian Kernighan'ın Sayma Yöntemi
Sayı sıfır olmadığı sürece döngüyü çalıştırın ve her seferinde en düşük konumdaki biti sıfırlayın. Döngü, 1 yapılmış bitlerin sayısı kadar çalışır; bu nedenle seyrek 1 biti sayımı için hızlıdır.
c = 0
while n:
n &= n - 1
c += 1İkinin Kuvvetini Kontrol Edin
İkinin pozitif bir kuvvetinde tam olarak bir tane 1 yapılmış bit bulunur; bu nedenle n & (n - 1) sonucu 0 olur. Tek bir AND işlemiyle bunu hemen anlayabilirsiniz.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Bit Sayısından Tek-Çiftlik
Bir sayının tek-çiftliği, 1 bitlerinin sayısının 2'ye bölümünden kalanıdır. Bu, birlerin sayısının tek mi çift mi olduğunu tek adımda belirler.
parity = (13).bit_count() & 1 # 1En Hızlı Aracı Seçin
Ham hız için bit_count kullanın; 1 yapılmış bitler üzerinde ilerlemek için n & (n-1) döngüsünü kullanın. Doğru aracı seçmek, sıkı zaman sınırlarını karşılamanızı sağlar. ⚡
Hızlı Kontrol
En düşük konumdaki 1 biti bulma yöntemini deneyin.
Özet: Bitleri Sayma
Birleri bit_count ile sayabilir, n & -n ile en düşük konumdaki biti ayırabilir ve n & (n-1) ile kaldırabilirsiniz. Güçlü tek satırlık çözümler. 🎉
Sıkça Sorulan Sorular
“Bitleri ve En Düşük Ayarlı Biti Sayma” dersi ücretsiz mi?
Evet — “Bitleri ve En Düşük Ayarlı Biti Sayma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“Bitleri ve En Düşük Ayarlı Biti Sayma” dersinde ne öğreneceğim?
popcount ve n & -n hilesini kullanın. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Bitleri ve En Düşük Ayarlı Biti Sayma” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- AND, OR, XOR ve Kaydırmalar
- Bit Ayarlama, Temizleme ve Değiştirme
- Bitleri ve En Düşük Ayarlı Biti Sayma
- Küçük Kümeler Olarak Bitmask'ler