Menghitung Bit dan Bit Set Terendah
Menggunakan popcount dan trik n & -n
Menghitung Bit dan Bit Set Terendah adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Menghitung Bit Bernilai 1
Banyak soal menanyakan berapa banyak bit yang aktif dalam sebuah bilangan, yang disebut jumlah bit 1. Ini muncul dalam ukuran subhimpunan, pemeriksaan paritas, dan penilaian. 🔢
Penghitungan Bawaan Python
Cara tercepat untuk menghitung bit yang aktif adalah metode bilangan bulat bit_count(). Tanpa perulangan dan tanpa kerumitan, cukup dapatkan jumlah bit bernilai 1.
print((13).bit_count()) # 0b1101 has 3 onesMenghitung dengan Bilangan Biner
Jika Anda lupa bit_count, ubah bilangan tersebut menjadi teks biner lalu hitung bit bernilai 1. Cara ini lebih lambat, tetapi jelas dan mudah diingat.
print(bin(13).count('1')) # 3Bit 1 Paling Rendah
Bit 1 paling rendah adalah angka 1 yang paling kanan dalam sebuah bilangan. Mengisolasinya merupakan langkah penting untuk pohon Fenwick dan trik subhimpunan nantinya.
Mengisolasinya dengan n dan -n
Trik terkenal n & -n hanya mempertahankan bit 1 paling rendah. Bilangan negatif dalam komplemen dua membuat trik ini bekerja seperti sulap.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Mengapa n dan -n Berfungsi
Meniadakan sebuah bilangan membalik semua bit lalu menambahkan 1, sehingga semua bit di bawah angka 1 paling rendah ikut terbalik. Operasi AND menyisakan hanya satu bit tersebut.
Menghapus Bit 1 Paling Rendah
Mengurangi 1 meminjam melalui nol-nol di bagian akhir, sehingga n & (n - 1) menghapus bit 1 paling rendah. Ulangi langkah ini untuk menghapus bit 1 satu per satu.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Penghitungan Brian Kernighan
Lakukan perulangan selama bilangan tersebut bukan nol, dan kosongkan bit paling rendah setiap kali. Perulangan berjalan sekali untuk setiap bit 1, sehingga cepat untuk jumlah bit 1 yang jarang.
c = 0
while n:
n &= n - 1
c += 1Memeriksa Pangkat Dua
Pangkat dua positif memiliki tepat satu bit 1, sehingga n & (n - 1) sama dengan 0. Satu operasi AND dapat memberi tahu Anda jawabannya seketika.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Paritas dari Jumlah Bit
Paritas sebuah bilangan hanyalah jumlah bit 1 modulo 2. Ini menjawab pertanyaan apakah jumlah bit 1 ganjil atau genap dalam satu langkah.
parity = (13).bit_count() & 1 # 1Memilih Alat Tercepat
Untuk kecepatan maksimum, gunakan bit_count; untuk menelusuri bit 1, gunakan perulangan n & (n-1). Memilih alat yang tepat membantu Anda memenuhi batas waktu yang ketat. ⚡
Pemeriksaan Singkat
Uji trik bit 1 paling rendah.
Ringkasan: Menghitung Bit
Anda dapat menghitung bit 1 dengan bit_count, mengisolasi bit paling rendah melalui n & -n, dan menghapusnya dengan n & (n-1). Satu baris kode yang sangat ampuh. 🎉
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menghitung Bit dan Bit Set Terendah” gratis?
Ya — teks lengkap “Menghitung Bit dan Bit Set Terendah” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menghitung Bit dan Bit Set Terendah”?
Menggunakan popcount dan trik n & -n Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Menghitung Bit dan Bit Set Terendah” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- AND, OR, XOR & Pergeseran
- Mengatur, Menghapus & Membalik Bit
- Menghitung Bit dan Bit Set Terendah
- Bitmask sebagai Set Kecil