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

指定された 32 ビット符號なし整數(shù)のビットを反転します。

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

• Java などの一部の言語では、符號なし整數(shù)型が存在しないことに注意してください。この場合、入力と出力の両方が符號付き整數(shù)型として與えられます。整數(shù)の內(nèi)部バイナリ表現(xiàn)は、符號付きか符號なしかに関係なく同じであるため、実裝には影響しません。

• Java では、コンパイラは 2 の補數(shù)表記を使用して符號付き整數(shù)を表します。したがって、例 2 では、入力は符號付き整數(shù) -3 を表し、出力は符號付き整數(shù) -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 ビット整數(shù)であることがわかっているため、各ビットの反転位置を簡単に計算できます。たとえば、0 番目は 31 番目、1 番目から 30 番目などに対応します。

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

n >>> idx

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

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

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.

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

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.

結(jié)果を 32 ビット整數(shù)として返す必要があります。そのためには、符號なし右シフト演算子を使用してトリックを?qū)g行できます。

n >>> idx

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

for (let i = 0; i < 32; i++) {
  let bit = (n >>> i) & 1;

  /* ... */
}

時間と空間の複雑さ

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

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

以上がLeetCode 瞑想: リバースビットの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。