颠倒二进制位（leetcode 190）

leetcode 190）"/>

颠倒二进制位（leetcode 190）

文章目录

• 1.问题描述
• 2.难度等级
• 3.热门指数
• 4.解题思路
• 5.实现示例
• • 5.1 C++
  • 5.2 Golang
• 参考文献

1.问题描述

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

示例 1：
输入：n = 43261596
输出：964176192 (00111001011110000010100101000000)
解释：无符号整数 43261596 的二进制串 00000010100101000001111010011100，反转后为 00111001011110000010100101000000，十进制为 964176192。

示例 2：
输入：n = 4294967293
输出：3221225471 (10111111111111111111111111111111)
解释：输入无符号整数 4294967293 的二进制串 11111111111111111111111111111101，反转后为 10111111111111111111111111111111，十进制为 3221225471。

2.难度等级

easy。

3.热门指数

★★★★☆

出题公司：虾皮、深信服。

4.解题思路

算法要现实的是将数值的位做个颠倒，只需遍历数值的每一位放到对应的位置即可，可以使用移位来实现。

实现步骤：

1. 从低位开始，获取低位值 0 或 1；
2. 将获取的比特位进行移位操作，移到其对应的位置；
3. 将移位的值进行累加；
4. 循环以上操作 32 次，注意当 n 为 0 时即可结束循环；

复杂度分析：

• 时间复杂度：O(1)。
• 空间复杂度：O(1)。

5.实现示例

5.1 C++

#include <iostream>
using namespace std;// reverseBits 颠倒二进制位。
uint32_t reverseBits(uint32_t n) {uint32_t r = 0;for (int i = 0; i < 32 && n > 0; ++i) {auto bit = n & 1;r |= bit << (31 - i);n >>= 1;}return r;
}int main() {cout << reverseBits(43261596) << endl;cout << reverseBits(4294967293) << endl;
}

运行输出：

964176192
3221225471

5.2 Golang

package mainimport ("fmt"
)// reverseBits 颠倒二进制位。
func reverseBits(n uint32) uint32 {r := uint32(0)for i := 0; i < 32 && n > 0; i++ {bit := n & 1r |= bit << (31 - i)n >>= 1}return r
}func main() {fmt.Println(reverseBits(43261596))fmt.Println(reverseBits(4294967293))
}

运行输出：

964176192
3221225471

参考文献

190. 颠倒二进制位 - leetcode