Easy

题目描述

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

示例 1：

输入：n = 43261596 输出：964176192 解释：

整数二进制
4326159600000010100101000001111010011100
96417619200111001011110000010100101000000

示例 2：

输入：n = 2147483644 输出：1073741822 解释：

整数二进制
214748364401111111111111111111111111111100
107374182200111111111111111111111111111110

约束条件：

  • 0 ≤ n ≤ 2³¹ - 2
  • n 是偶数

进阶： 如果这个函数被频繁调用，你该如何优化它？

解题思路

这道题要求我们将32位整数的二进制位进行颠倒。有几种常见的解法：

方法一：逐位处理（推荐） 最直观的方法是逐位提取原数字的最低位，然后将其添加到结果的最高位。具体过程：

  1. 从右到左逐个提取原数字的二进制位
  2. 将提取的位从左到右放入结果中
  3. 重复32次完成所有位的颠倒

方法二：分治法优化 可以使用分治的思想，先交换相邻的位，再交换相邻的2位组，依此类推。这种方法的优势是减少了循环次数，但代码复杂度较高。

方法三：查表法（适用于频繁调用） 如果函数被频繁调用，可以预先计算所有8位数字（0-255）的颠倒结果，然后将32位数字分成4个8位段分别查表，最后组合结果。

对于本题，方法一最容易理解且效率足够，是最推荐的解法。

代码实现

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

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result

public class Solution {
    public int ReverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
}

var reverseBits = function(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;  // 使用无符号右移
    }
    return result >>> 0;  // 确保返回无符号32位整数
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)固定循环32次，与输入大小无关
空间复杂度O(1)只使用了常数级别的额外空间

相关题目