123.颠倒二进制位
题目
颠倒给定的 32 位有符号整数的二进制位。
示例 1：
-
输入：n = 43261596
-
输出：964176192
解释：
整数 二进制
43261596 00000010100101000001111010011100
964176192 00111001011110000010100101000000
思路：逐位提取并构建
方法一：逐位操作（最简单直观）
- 初始化结果 res = 0。
- 循环 32 次（因为 32 位整数）：
- 将 res 左移一位，腾出最低位。
- 取 n 的最低位（n & 1），加到 res 的最低位。
- 将 n 右移一位，丢弃已处理的最低位。
- 返回 res。
这个过程就像：
你有一摞卡片（n 的二进制位），每次从最底下抽一张（取最低位），放在新的一摞的最上面（res 左移后加上该位）。 重复 32 次，原来最底下的卡片就到了新摞的最顶上，实现了反转。
class Solution {
// you need treat n as an unsigned value
fun reverseBits(n: Int): Int {
var num = n
var res = 0
for (i in 0 until 32) {
res = res shl 1 // 结果左移一位
res = res or (num and 1) // 取 n 最低位加到结果
num = num shr 1 // n 右移一位
}
return res
}
}
方法二：分治法（更高效，但稍复杂）
将 32 位分成两半，分别反转后再交换位置。可以递归地进行： - 先交换相邻的 1 位（奇偶位互换）。 - 再交换相邻的 2 位。 - 再交换相邻的 4 位。 - 再交换相邻的 8 位。 - 最后交换相邻的 16 位。
- 每一步都用位掩码和移位操作实现，时间复杂度 O(log n)（即 O(1) 常数时间）。
复杂度
- 时间复杂度:
- 空间复杂度:
- 邮箱 ：charon.chui@gmail.com
- Good Luck!