Meditasi LeetCode: Jumlahnya

Mari kita mulakan dengan penerangan untuk yang ini:

Diberikan integer positif n, tulis fungsi yang mengembalikan bilangan bit set dalam perwakilan binarinya (juga dikenali sebagai pemberat Hamming).

Contohnya:

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

Atau:

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

Atau:

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

---

Seperti yang kami nyatakan dalam pengenalan bab dalam catatan sebelumnya, bit set merujuk kepada bit dengan nilai 1.

Jadi, apa yang perlu kita lakukan ialah mengira 1 bit.

Satu cara untuk melakukannya ialah menukar nombor kepada rentetan dan hanya mengira 1s. Atau, kita boleh menukarnya kepada tatasusunan dan menapis keluar 0s, dan mendapatkan panjangnya. Tetapi, terdapat pendekatan lain di mana kita boleh menggunakan manipulasi bit.

Kita boleh mengeluarkan bit yang ditetapkan (bit yang mempunyai nilai 1) sehingga nombornya menjadi 0.

Perkara yang baik untuk diketahui ialah n - 1 ialah set paling kanan versi dialih keluar n.

Contohnya, jika n ialah 0010, n - 1 ialah 0001.

Atau, jika n ialah 0110, n - 1 ialah 0101.

Nota Tidak kira sama ada n - 1 memperkenalkan 1 lain kerana kami sedang melakukan operasi DAN untuk mengira bit yang ditetapkan.

Note

It does not matter whether n - 1 introduces other 1s because we are doing the AND operation to count the set bits.
For example, if n is 0000, then n - 1 is 0111. Their AND will be 0000.
Or, if n is 0010, then n - 1 is 0001. The rightmost set bit of n is 0 in n - 1, and that's all that matters.

Contohnya, jika n ialah 0000, maka n - 1 ialah 0111. AND mereka akan menjadi 0000. Atau, jika n ialah 0010, maka n - 1 ialah 0001. Bit set paling kanan bagi n ialah 0 in n - 1, dan itu sahaja yang penting.

Kita boleh mencipta gelung yang berjalan selagi terdapat 1 bit dalam n, mengira setiap satu semasa kita pergi. Juga setiap kali, kita boleh melakukan operasi DAN

dengan n dan kurang 1 daripadanya (n & (n - 1)).

Penyelesaian TypeScript yang mudah kelihatan seperti ini:

function hammingWeight(n: number): number {
  let result = 0;
  while (n > 0) {
    n &= (n - 1);
    result++;
  }

  return result;
}

Note

We are using the bitwise AND assignment operator to assign the value to n.

Kerumitan masa dan ruang

Kerumitan masa, saya rasa, $O(logn)$O(log n) — Dalam kes yang paling teruk apabila semua bit ditetapkan, kami akan melalui gelung $logn$log n kali (bilangan bit dalam perwakilan binari nombor $n$n akan menjadi $logn$log n ).

Kerumitan ruang akan tetap ( $O(1)$O(1) ) kerana tiada penggunaan memori tambahan yang akan meningkat apabila input meningkat.

---

Masalah seterusnya yang akan kita lihat ialah Mengira Bit. Sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Jumlahnya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!