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) .

---

接下来，我们将看看 Missing Number。在那之前，祝您编码愉快。

以上是LeetCode 冥想：反转位的详细内容。更多信息请关注PHP中文网其他相关文章！