数値を変換するための最小ビット反転数

2220。数値を変換するための最小ビット反転

難易度: 簡単

トピック: ビット操作

数値 x のビット反転は、x のバイナリ表現内のビットを選択し、それを 0 から 1 または 1 から 0 に反転します。

• たとえば、forx = 7、バイナリ表現は 111 で、任意のビット (表示されていない先行ゼロを含む) を選択して反転できます。右から最初のビットを反転すると 110 が得られ、右から 2 番目のビットを反転すると 101 が得られ、右から 5 番目のビット (先行ゼロ) を反転すると 10111 が得られます。

2 つの整数のスタートとゴールを指定すると、スタートとゴールを変換するためのビット 反転の最小数を返します。

例 1:

• 入力: 開始 = 10、目標 = 7
• 出力: 3
• 説明: 10 と 7 の 2 進表現は、それぞれ 1010 と 0111 です。 10 を 7 に 3 つのステップで変換できます。
  最初のビットを右から反転します: 1010 -> 1011.
  右から 3 番目のビットを反転します: 1011 -> 1111.
  右から 4 番目のビットを反転します: 1111 -> 0111.
  3 ステップ未満で 10 を 7 に変換することはできないことがわかります。したがって、3 を返します。

例 2:

• 入力: 開始 = 3、目標 = 4
• 出力: 3
• 説明: 3 と 4 の 2 進表現は、それぞれ 011 と 100 です。 3 つのステップで 3 を 4 に変換できます。
  最初のビットを右から反転します: 011 -> 010.
  右から 2 番目のビットを反転します: 010 -> 000.
  右から 3 番目のビットを反転します: 000 -> 100.
  3 ステップ未満では 3 を 4 に変換できないことがわかります。したがって、3 を返します。

制約:

0 9

ヒント:

スタートとゴールのビットの値が異なる場合は、そのビットを反転する必要があります。
XOR 演算を使用して、ビット フリップが必要なビットを決定することを検討してください。

解決策:

開始と終了の間で何ビット位置が異なるかを決定する必要があります。これは、2 つの数値が異なる各ビット位置に 1 を返す XOR 演算 (^) を使用して簡単に実現できます。

手順:

スタートとゴールの間で XOR 演算を実行します。結果は、スタートとゴールが異なるすべての位置に 1 が含まれる数字になります。
結果のバイナリ表現 (つまり、ハミング距離) に 1 がいくつ存在するかを数えます。
1 の数により、必要なビット 反転の最小数が決まります。

このソリューションを PHP で実装してみましょう:

2220。数値を変換するための最小ビット反転

<?php
/**
 * @param Integer $start
 * @param Integer $goal
 * @return Integer
 */
function minBitFlips($start, $goal) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minBitFlips(10, 7);  // Output: 3
echo "\n";
echo minBitFlips(3, 4);   // Output: 3
?>

説明：

^ (XOR) 演算は、開始と終了の各ビットを比較します。ビットが異なる場合、結果の対応するビットは 1 になります。
次に、結果内の 1 の数を数えます。これにより、異なるビットの数、つまり必要なビット 反転の数がわかります。
& 1 演算は最後のビットが 1 かどうかをチェックし、>>= 1 は数値を右にシフトして次のビットを処理します。

時間計算量:

時間計算量は (O(log N)) です。数値の各ビットをチェックしているため、(N) は開始または終了の大きい方です。最悪の場合、32 ビット整数のすべてのビットをループします (PHP 5.6 はシステムに応じて 32 ビットまたは 64 ビット整数で動作するため)。

出力：

開始 = 10、目標 = 7 の場合、出力は 3 です。
開始 = 3 および目標 = 4 の場合、出力は 3 です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で

リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が数値を変換するための最小ビット反転数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。