英文原文
Reverse bits of a given 32 bits unsigned integer.
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
-3and the output represents the signed integer-1073741825.
Example 1:
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.
Example 2:
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.
Constraints:
- The input must be a binary string of length
32
Follow up: If this function is called many times, how would you optimize it?
中文题目
颠倒给定的 32 位无符号整数的二进制位。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数
-3，输出表示有符号整数-1073741825。
示例 1：
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：n = 11111111111111111111111111111101 输出：3221225471 (10111111111111111111111111111111) 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：
- 输入是一个长度为
32的二进制字符串
进阶: 如果多次调用这个函数，你将如何优化你的算法？
通过代码
高赞题解
各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 64 天。今天力扣上的每日一题是「190. 颠倒二进制位」。
解题思路
今天的题目是要求将一个数字，把其二进制翻转，求得到的另外一个二进制数。
方法一：循环
这是最容易想到的方法了，每次把 res 左移，把 $n$ 的二进制末尾数字，拼接到结果 res 的末尾。然后把 $n$ 右移。
举一个 8 位的二进制进行说明：
| i | n | res |
|---|---|---|
| - | 11001001 | - |
| 0 | 1100100 | 1 |
| 1 | 110010 | 10 |
| 2 | 11001 | 100 |
| 3 | 1100 | 1001 |
| 4 | 110 | 10010 |
| 5 | 11 | 100100 |
| 6 | 1 | 1001001 |
| 8 | - | 10010011 |
代码如下：
[]class Solution: # @param n, an integer # @return an integer def reverseBits(self, n): res = 0 for i in range(32): res = (res << 1) | (n & 1) n >>= 1 return res
[]class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t res = 0; for (int i = 0; i < 32; ++i) { res = (res << 1) | (n & 1); n >>= 1; } return res; } };
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
方法二：分而治之
有另外一种不使用循环的做法，类似于归并排序。
其思想是分而治之，把数字分为两半，然后交换这两半的顺序；然后把前后两个半段都再分成两半，交换内部顺序……直至最后交换顺序的时候，交换的数字只有 1 位。
以一个 8 位的二进制数字为例：
代码如下：
[]class Solution: # @param n, an integer # @return an integer def reverseBits(self, n): n = (n >> 16) | (n << 16); n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n;
[]class Solution { public: uint32_t reverseBits(uint32_t n) { n = (n >> 16) | (n << 16); n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } };
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
刷题心得
位运算还是很有意思的。
参考资料：
OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。
祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 140778 | 200836 | 70.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 整数反转 | 简单 |
| 位1的个数 | 简单 |
