LeetCode 冥想：反轉位

Reverse Bits 的描述非常簡短：

反轉給定 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個，依此類推。

但是我們正在進行位元操作，這意味著我們必須一位一位地處理。
因此，我們可以運行一個 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 進行與運算視為乘法恆等式（例如， $7\cdot 1=77\; 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 < 32; i++) {
  let bit = (n >>> i) & 1;

  /* ... */
}

時間和空間複雜度

我們知道輸入和結果總是32 位元整數（並且，我們不必使用任何其他額外的資料結構），我們也運行循環32 次，這是一個固定的數字，所以時間複雜度和空間複雜度都是 $O(1))$O(1) O(1)

---

. 接下來，我們將看看 Missing Number。在那之前，祝您編碼愉快。

以上是LeetCode 冥想：反轉位的詳細內容。更多資訊請關注PHP中文網其他相關文章！