Kira Bit dan Bit Set Terendah
Gunakan popcount dan helah n & -n.
Kira Bit dan Bit Set Terendah ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Mengira Bit 1
Banyak masalah meminta anda mengira bilangan bit yang ditetapkan dalam nombor, yang dipanggil bilangan bit 1. Ia muncul dalam saiz subhimpunan, semakan pariti dan pemarkahan. 🔢
Kiraan Terbina Dalam Python
Cara terpantas untuk mengira bit yang ditetapkan ialah kaedah integer bit_count(). Tiada gelung, tiada kerumitan, hanya bilangan bit 1.
print((13).bit_count()) # 0b1101 has 3 onesKira dengan bin dan count
Jika anda terlupa bit_count, tukarkan nombor kepada teks perduaan dan hitung bit 1. Cara ini lebih perlahan tetapi jelas dan mudah diingati.
print(bin(13).count('1')) # 3Bit 1 Terendah
Bit 1 terendah ialah 1 yang paling kanan dalam sesuatu nombor. Mengasingkannya ialah langkah penting untuk pepohon Fenwick dan helah subhimpunan yang akan datang.
Asingkan dengan n dan -n
Helah terkenal n & -n hanya mengekalkan bit 1 terendah. Nombor negatif dalam pelengkap dua menjadikan helah ini berfungsi seperti sihir.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Mengapa n dan -n Berfungsi
Penafian membalikkan semua bit dan menambah 1, jadi semua bit di bawah 1 terendah diterbalikkan. Operasi AND meninggalkan hanya satu bit itu.
Buang Bit 1 Terendah
Menolak 1 meminjam melalui sifar di hujung, jadi n & (n - 1) memadamkan bit 1 terendah. Ulanginya untuk menanggalkan bit 1 satu demi satu.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Kiraan Brian Kernighan
Ulang gelung selagi nombor bukan sifar dan kosongkan bit terendah setiap kali. Gelung itu berjalan sekali bagi setiap bit 1, jadi ia pantas untuk bilangan bit 1 yang jarang.
c = 0
while n:
n &= n - 1
c += 1Semak Kuasa Dua
Kuasa dua positif mempunyai tepat satu bit 1, jadi n & (n - 1) bersamaan 0. Satu operasi AND sudah cukup untuk mengetahuinya serta-merta.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Pariti daripada Bilangan Bit
Pariti sesuatu nombor hanyalah bilangan bit 1 modulo 2. Ia menjawab soalan tentang bilangan bit 1 ganjil atau genap dalam satu langkah.
parity = (13).bit_count() & 1 # 1Pilih Alat Terpantas
Untuk kelajuan maksimum, gunakan bit_count; untuk melawati bit 1, gunakan gelung n & (n-1). Memilih alat yang betul membantu memenuhi had masa yang ketat. ⚡
Semakan Pantas
Uji helah bit 1 terendah.
Rumusan: Mengira Bit
Anda boleh mengira bit 1 dengan bit_count, mengasingkan bit terendah melalui n & -n, dan menanggalkannya dengan n & (n-1). Baris tunggal yang berkuasa. 🎉
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Kira Bit dan Bit Set Terendah” percuma?
Ya — teks penuh “Kira Bit dan Bit Set Terendah” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Kira Bit dan Bit Set Terendah”?
Gunakan popcount dan helah n & -n. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Kira Bit dan Bit Set Terendah” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- AND, OR, XOR dan Anjakan
- Tetapkan, Kosongkan dan Togol Bit
- Kira Bit dan Bit Set Terendah
- Bitmask sebagai Set Kecil