JavaScriptのデータ構造とアルゴリズムを詳しく解説

整数を入力し、その数値のバイナリ表現で表される1の数を出力する関数を実装してください。たとえば、9 を 2 進数で 1001 と表すと、2 ビットが 1 になります。したがって、9 を入力すると、関数は 2 を出力します。まず、2進数1の解法ですが、ここで最も考えるべきはビット演算に関する演算子です。合計 5 つの演算があります: AND (&)、OR (|)、XOR (^)、右シフト (>>)、および左シフト (

無限ループを引き起こす可能性のある最初の解決策:
アイデア 1: まず、指定した整数がこの数値の右端の部分が 1 であるかどうかを判断します。 1 の場合は、カウンターを与え、それに 1 を加えます。次に、入力された整数を 1 ビット右にシフトし、整数が 0 になるまでシフトを続けてカウンタを出力します。

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

このアルゴリズムは、符号なしの数値に対しては問題ありませんが、符号付きの数値に対しては大きな問題となり、無限ループを引き起こす可能性が非常に高くなります。 n が負の数の場合、n は右にシフトされ、(データが負であることを保証するために) 最上位ビットに 1 が追加されるため、最終的には無限ループが形成されます。例：0x80000000、1つ右にずらすと0xC0000000となります。これは負の数のシフトであるため、シフトされた数が負の数であることを確認する必要があり、最上位ビットは常に 1 になります。これは、最終的にはこの数が常に無限ループすることを意味します。

アイデア 2: 1 を移動するには、まず最下位ビットが 1 であるかどうかを判断し、次に 1 を 2 に移動します。次に、それを整数比と比較して、最後から 2 番目の桁が 1 であるかどうかを判断します。 。 。このようにして、最終的に効果が得られ、オール１の数が得られる。

function NumberOf1(n) {

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

最後に、最良の方法を提供します。

アイデア 3: 整数から 1 を減算し、元の整数との AND 演算を実行します。整数の右端の 1 は 0 に変換され、1 の後の 0 はすべて 1 に変換されます。そして、整数の 2 進数にある 1 の数だけこの演算を実行できます。最後に、カウンタを使用して演算の回数を求め、カウンタを出力するだけです。

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

関連する推奨事項:

PHP のデータ構造: DS 拡張機能の詳細な説明

順次リンク リストとリンク線形テーブルの PHP データ構造の例

単一リンク リストと循環リンクの JavaScript データ構造リストの例の共有

以上がJavaScriptのデータ構造とアルゴリズムを詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。