题目描述
题目链接:190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
例子
例子 1
Input:
n = 00000010100101000001111010011100
Output:964176192 (00111001011110000010100101000000)
Explanation: The input binary string00000010100101000001111010011100
represents the unsigned integer43261596
, so return964176192
which its binary representation is00111001011110000010100101000000
.
例子 2
Input:
n = 11111111111111111111111111111101
Output:3221225471 (10111111111111111111111111111111)
Explanation:The input binary string11111111111111111111111111111101
represents the unsigned integer4294967293
, so return3221225471
which its binary representation is10111111111111111111111111111111
.
Follow Up
If this function is called many times, how would you optimize it?
Note
- Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
- In Java, the compiler represents the signed integers using
2's complement notation
. Therefore, in Example 2 above, the input represents the signed integer-3
and the output represents the signed integer-1073741825
.
Constraints
- The input must be a binary string of length
32
解题思路
用基本位操作即可,代码如下:
#include <cstdint>
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
int count = 0;
while (count < 31) {
ans |= (n & 0x1);
n >>= 1;
ans <<= 1;
count++;
}
ans |= (n & 0x1);
return ans;
}
};
- 时间复杂度:
O(1)
- 空间复杂度:
O(1)
GitHub 代码同步地址: 190.ReverseBits.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions