LeetCode 瞑想: リバースビット

リバース ビットの説明は非常に簡単です:

指定された 32 ビット符号なし整数のビットを反転します。

次の注意事項もあります:

• Java などの一部の言語では、符号なし整数型が存在しないことに注意してください。この場合、入力と出力の両方が符号付き整数型として与えられます。整数の内部バイナリ表現は、符号付きか符号なしかに関係なく同じであるため、実装には影響しません。

• Java では、コンパイラは 2 の補数表記を使用して符号付き整数を表します。したがって、例 2 では、入力は符号付き整数 -3 を表し、出力は符号付き整数 -1073741825 を表します。

例:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

または:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

制約では、入力は長さ 32 の バイナリ文字列でなければならないとも述べられています。

---

入力が 32 ビット整数であることがわかっているため、各ビットの反転位置を簡単に計算できます。たとえば、0 番目は 31 番目、1 番目から 30 番目などに対応します。

しかし、私たちはビット操作を行っているので、各ビットを 1 つずつ処理する必要があります。
したがって、for ループを実行してそれを行うことができます。毎回、インデックスによってビットを右端の位置にシフトできます。これは次のようになります。

n >>> idx

ビット (0 か 1 か) の取得は、1 との AND 演算で簡単に行うことができます。
ビットが 0 の場合、0 & 1 は 0 になります。
1 の場合、1 & 1 の結果は 1 になります。

メモ

Note

We can think of ANDing with 1 as the multiplicative identity (for example, $7\cdot 1=7$7⋅1=7 ).

1 との AND 演算 を乗算単位として考えることができます (たとえば、 $7\cdot 1=7$7⋅1=7 スパン> ). テーブル>

まず、ビットを取得します。

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

次に、手持ちのビットを逆の位置に置く必要があります。そのために、ビットを左にシフトし、結果を加算します。

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

結果を 32 ビット整数として返す必要があります。そのためには、符号なし右シフト演算子を使用してトリックを実行できます。

n >>> idx

そして、最終的な解決策は次のようになります:

for (let i = 0; i >> i) & 1;

  /* ... */
}

時間と空間の複雑さ

入力と結果は常に 32 ビット整数であることがわかっています (そして、他の追加のデータ構造を使用する必要はありません)。同様にループを 32 回実行しますが、これは固定数であるため、時間と空間の複雑さは両方とも $O(1)$O(1) .

---

次に、Missing Number について見ていきます。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: リバースビットの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。