Detaillierte Erläuterung der Javascript-Datenstruktur und des Algorithmus

Bitte implementieren Sie eine Funktion, die eine Ganzzahl eingibt und die Anzahl der Einsen ausgibt, die durch die binäre Darstellung der Zahl dargestellt werden. Wenn beispielsweise 9 binär als 1001 dargestellt wird, sind 2 Bits 1. Wenn Sie also 9 eingeben, gibt die Funktion 2 aus. Für die Lösung der Binärzahl 1 sollten wir hier zunächst vor allem an einige Operatoren für Bitoperationen denken. Insgesamt gibt es fünf Operationen, nämlich AND (&), OR (|), XOR (^), Rechtsverschiebung (>>) und Linksverschiebung (<<).

Die erste Lösung, die eine Endlosschleife verursachen kann:
Idee 1: Beurteilen Sie zunächst die von Ihnen angegebene ganze Zahl und prüfen Sie, ob der rechte Teil dieser Zahl 1 ist. Wenn es 1 ist, geben Sie einen Zähler ein und addieren Sie 1 dazu. Verschieben Sie dann die eingegebene Ganzzahl um ein Bit nach rechts und verschieben Sie sie weiter, bis die Ganzzahl 0 wird, und geben Sie dann den Zähler aus.

function NumberOf1(n)
{
  let count = 0;
  while(n) {
    if(n & 1) {
      count ++;
    }
    n = n >> 1;
  }
  return count;
}
console.log(NumberOf1(9));</p>
<p>Dieser Algorithmus hat kein Problem für vorzeichenlose Zahlen, stellt jedoch ein großes Problem für vorzeichenbehaftete Zahlen dar und führt sehr wahrscheinlich zu einer Endlosschleife. Wenn n eine negative Zahl ist, wird n nach rechts verschoben und 1 zum höchsten Bit addiert (um sicherzustellen, dass die Daten negativ sind), sodass sich schließlich eine Endlosschleife bildet. Beispiel: 0x80000000, zu diesem Zeitpunkt tritt ein Problem auf. Wenn es um eine Position nach rechts verschoben wird, wird es zu 0xC0000000. Da es sich um eine Verschiebung einer negativen Zahl handelt, muss sichergestellt sein, dass die verschobene Zahl eine negative Zahl ist, das höchste Bit also immer 1 ist, was bedeutet, dass diese Zahl am Ende immer in einer Endlosschleife durchlaufen wird. </p>
<p> Idee 2: Verschieben Sie 1, bestimmen Sie zunächst, ob das niedrigste Bit 1 ist, und verschieben Sie dann 1 nach 2. Vergleichen Sie es dann mit dem ganzzahligen Verhältnis, um festzustellen, ob die vorletzte Ziffer 1 ist, und so weiter. . . Auf diese Weise kann am Ende ein Effekt erzielt und die Anzahl aller Einsen ermittelt werden. </p>
<pre class="brush:php;toolbar:false">function NumberOf1(n) {

  let count = 0;
  let flag = 1;
  while(flag) {
    if(n & flag) {
      count ++;
    }
    flag = flag << 1;
  }
  return count;
}
console.log(NumberOf1(9));

Endlich bieten wir die beste Methode.

Idee 3: Subtrahieren Sie 1 von einer Ganzzahl und führen Sie dann eine UND-Operation mit der ursprünglichen Ganzzahl durch. Die 1 auf der rechten Seite der Ganzzahl wird in 0 umgewandelt und alle Nullen nach der 1 werden verwandelte sich in 1. Dann kann diese Operation so oft wie möglich ausgeführt werden, so viele Einsen es im Binärsystem einer ganzen Zahl gibt. Bestimmen Sie abschließend einfach die Anzahl der Operationen mithilfe des Zählers und geben Sie den Zähler aus.

//更好的解法
function NumberOf1(n) {
  let count = 0;
  while(n) {
    count ++;
    n = (n-1) & n;
  }
  return count;
}
console.log(NumberOf1(9));

Verwandte Empfehlungen:

Datenstruktur in PHP: Detaillierte Erklärung der DS-Erweiterung

Die Reihenfolge von PHP Datenstruktur Beispiele für verknüpfte Listen und verknüpfte lineare Listen

Teilen von Beispielen für einfach verknüpfte Listen und zirkulär verknüpfte Listen in JavaScript-Datenstrukturen

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Javascript-Datenstruktur und des Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!