190. 颠倒二进制位

原题链接

题目描述

颠倒给定的 32 位无符号整数的二进制位。

示例1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：

• 输入是一个长度为 32 的二进制字符串
• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

---

思路

(位运算) \(O(1)\)

使用位运算 n >> i & 1 可以取出 \(n\) 的第 \(i\) 位二进制数。 我们从小到大依次取出 \(n\) 的所有二进制位，然后逆序累加到另一个无符号整数中。

时间复杂度分析：C++中所有位运算的计算量都是1，比如 n >> 10，将 n 右移10位，计算量是1而不是10。所以在该问题中，我们总共进行了 4 * 32 次运算，所以时间复杂度是 \(O(1)\)。

代码

C++

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) + (n >> i & 1);
        }
        return res;
    }
};