Number of 1 Bits

Q: Berapa kompleksitas waktu Number of 1 Bits?

Perulangan shift berjalan sekali untuk setiap digit biner: O(log n) , paling banyak 31 langkah di sini. Perulangan n & (n-1) berjalan sekali untuk setiap bit 1: O(k) , dengan k sebagai jawabannya. Keduanya menggunakan ruang tambahan O(1) .

MudahManipulasi bit

+10

Kamu mendapatkan bilangan bulat non-negatif n. Tuliskan n dalam biner dan kembalikan jumlah digitnya yang bernilai 1. Jumlah ini juga disebut jumlah bit aktif, jumlah populasi, atau bobot Hamming. Contohnya, 6 ditulis sebagai 110 dalam biner, jadi memiliki dua bit bernilai 1.

Fungsi

hammingWeight(n: integer) → integer

ninteger: bilangan bulat non-negatif yang muat dalam int bertanda 32-bit
Mengembalikaninteger: jumlah digit 1 dalam bentuk biner dari n

Batasan

0 ≤ n ≤ 2³¹-1

Contoh

Input: n = 11
Output: 3
Penjelasan: 11 dalam biner adalah 1011, yaitu 8 + 2 + 1. Tiga dari empat digit binernya adalah 1, jadi jawabannya 3.

Input: n = 128
Output: 1
Penjelasan: 128 adalah 2^7, ditulis 10000000: satu angka 1 diikuti angka nol, jadi jawabannya adalah 1.

Pertanyaan lanjutan

Jika fungsi ini dijalankan jutaan kali, bagaimana kamu dapat menghitung bit dari angka 32-bit dengan empat pencarian dalam tabel berisi 256 hitungan yang telah dihitung sebelumnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Telusuri digit biner dari n tanpa membuat string. Membaca bit terakhir lalu menggesernya hingga hilang membutuhkan satu langkah untuk setiap digit biner, hingga 31 langkah. Menghapus bit 1 terendah dengan n & (n-1) membutuhkan satu langkah untuk setiap bit 1, persis sebanyak jumlah jawabannya.

Periksa bit terakhir lalu geser ke kanan

Intuisi

n & 1 adalah digit biner terakhir dari n: 1 jika n ganjil, 0 jika genap. Tambahkan digit itu ke hitungan. Lalu n >> 1 menghapus digit tersebut dan memindahkan digit berikutnya ke posisi terakhir; untuk bilangan non-negatif, operasi ini sama dengan pembagian dengan 2 yang dibulatkan ke bawah. Untuk 11, 1011, bit terakhir terbaca 1, 1, 0, dan 1 saat n mengecil hingga 0: ada tiga bit 1.

Perulangan berhenti saat n bernilai 0, jadi tidak pernah memproses nol di depan: sekitar log2(n) langkah, 8 untuk 128 dan paling banyak 31. Perulangan ini hanya menyimpan n dan hitungan.

Algoritma

Mulai penghitung dari 0.
Selama n lebih besar dari 0, tambahkan n & 1 ke penghitung.
Geser n ke kanan sebanyak satu bit.
Saat n mencapai 0, kembalikan penghitung.

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

Hapus bit bernilai 1 paling rendah dengan n & (n-1)

Intuisi

Mengurangi 1 mengubah bit 1 terendah menjadi 0 dan setiap bit 0 di bawahnya menjadi 1, serta membiarkan bit di atasnya tidak berubah. Jadi, n & (n-1) mempertahankan bit-bit atas dan menghapus bit 1 terendah: 12 adalah 1100, 11 adalah 1011, dan 1100 & 1011 adalah 1000.

Setiap langkah menghapus tepat satu bit 1, jadi jumlah langkah hingga n menjadi 0 adalah jawabannya. 128 memerlukan 1 langkah, bukan 8, meskipun 2^31-1 tetap memerlukan 31 langkah. Lua 5.1 tidak memiliki operator bit, jadi versinya mencari bit 1 terendah dengan membagi dua lalu menguranginya; perulangan tetap berjalan sekali untuk setiap bit 1.

Algoritma

Mulai penghitung dari 0.
Selama n bukan 0, ganti n dengan n & (n-1).
Tambahkan 1 ke penghitung setelah setiap penggantian.
Kembalikan penghitung.

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

Jebakan dan kasus tepi

Melakukan perulangan selama n > 1. Perulangan berhenti sebelum bit 1 terakhir dan mengembalikan 0 untuk n = 1.
Membagi dengan bilangan float. Di JavaScript, Lua, dan R, 11 / 2 adalah 5.5 dan sisa pembagian berikutnya berupa pecahan. Bulatkan ke bawah dengan Math.floor, math.floor, atau %/%, atau gunakan pergeseran bit.
Menulis n & 1 di Lua 5.1. Lua 5.1 tidak memiliki operator bit, sehingga kode tidak dapat dikompilasi. Gunakan n % 2 dan math.floor(n / 2).

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Number of 1 Bits?

Perulangan shift berjalan sekali untuk setiap digit biner: O(log n), paling banyak 31 langkah di sini. Perulangan n & (n-1) berjalan sekali untuk setiap bit 1: O(k), dengan k sebagai jawabannya. Keduanya menggunakan ruang tambahan O(1).

Apakah ada fungsi bawaan untuk menghitung bit yang bernilai 1?

Sebagian besar bahasa pemrograman memiliki fungsi ini, yang sering kali didukung oleh satu instruksi prosesor: Integer.bitCount di Java, __builtin_popcount di GCC, bits.OnesCount di Go, count_ones di Rust, dan int.bit_count di Python 3.10 dan versi yang lebih baru. Saat wawancara, tulis perulangannya dan sebutkan fungsi bawaan tersebut.

Apa perbedaan antara bobot Hamming dan jarak Hamming?

Hamming weight suatu angka adalah jumlah digit binernya yang bernilai 1, dan itulah yang dikembalikan oleh soal ini. Hamming distance antara dua angka adalah jumlah posisi bit yang berbeda: hitung bit 1 dari a ^ b, karena XOR menetapkan tepat posisi-posisi tempat keduanya berbeda.

def hammingWeight(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 11

Output yang diharapkan