LeetCode-Meditationen: Anzahl seiner

Beginnen wir mit der Beschreibung für dieses:

Schreiben Sie bei einer gegebenen positiven ganzen Zahl n eine Funktion, die die Anzahl der gesetzten Bits in ihrer Binärdarstellung (auch als Hamming-Gewicht bekannt) zurückgibt.

Zum Beispiel:

Input: n = 11
Output: 3

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

Oder:

Input: n = 128
Output: 1

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

Oder:

Input: n = 2147483645
Output: 30

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

---

Wie wir in der Kapiteleinleitung im vorherigen Beitrag erwähnt haben, bezieht sich ein gesetztes Bit auf ein Bit mit dem Wert 1.

Was wir also tun müssen, ist, 1 Bit zu zählen.

Eine Möglichkeit besteht darin, die Zahl in eine Zeichenfolge umzuwandeln und einfach die Einsen zu zählen. Oder wir können das in ein Array umwandeln, die Nullen herausfiltern und seine Länge ermitteln. Aber es gibt noch einen anderen Ansatz, bei dem wir Bitmanipulation nutzen können.

Wir können die gesetzten Bits (Bits, die den Wert 1 haben) entfernen, bis die Zahl 0 wird.

Gut zu wissen ist, dass n - 1 die am weitesten rechts entfernte Version von n ist.

Wenn n beispielsweise 0010 ist, ist n - 1 0001.

Oder, wenn n 0110 ist, ist n - 1 0101.

Hinweis Es spielt keine Rolle, ob n - 1 andere Einsen einführt, da wir die UND-Operation ausführen, um die gesetzten Bits zu zählen.

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.

Wenn n zum Beispiel 0000 ist, dann ist n - 1 0111. Ihr UND wird 0000 sein. Oder, wenn n 0010 ist, dann ist n - 1 0001. Das am weitesten rechts gesetzte Bit von n ist 0 in n - 1, und das ist alles, was zählt.

Wir können eine Schleife erstellen, die so lange läuft, wie 1 Bits in n vorhanden sind, und dabei jedes einzelne zählen. Außerdem können wir jedes Mal eine AND

-Operation mit n und 1 weniger davon (n & (n - 1)) durchführen.

Eine einfache TypeScript-Lösung sieht so aus:

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.

Zeit- und Raumkomplexität

Die zeitliche Komplexität ist, glaube ich, $O(logn)$O(log n) — Im schlimmsten Fall, wenn alle Bits gesetzt sind, durchlaufen wir die Schleife $logn$log n mal (die Anzahl der Bits in der binären Darstellung einer Zahl). $n$n wird sein $logn$log n ).

Die Raumkomplexität wird konstant sein ( $O(1)$O(1) ), da es keine zusätzliche Speichernutzung gibt, die mit zunehmender Eingabe zunimmt.

---

Das nächste Problem, das wir uns ansehen werden, ist das Zählen von Bits. Bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Anzahl seiner. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!