LeetCode 190 Reverse Bits 反转二进制位从逐位提取到位运算分治的最优解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 190Reverse Bits展开讲解如何将给定的 32 位无符号整数的二进制位完全反转。你将掌握三条由浅入深的解题路径字符串暴力法、逐位提取的位运算法以及经典的分治掩码最优法并结合本仓库GitHub_Trending/leetcode1/leetcode中 Python、C、C、Java、JavaScript、Go、Rust、Kotlin、Swift、C#、TypeScript、Ruby 十二种语言的实际实现验证算法细节最终达到 O(1) 时间、O(1) 空间的求解要求。1. 问题与核心观察题目要求给定一个 32 位无符号整数反转其二进制位例如输入43261596二进制00000010100101000001111010011100输出应为964176192二进制00111001011110000010100101000000。在动手写代码前先建立两个关键认知对应 hints/reverse-bits.md 中 Hint 1 与 Hint 2 的引导位置映射规律反转后原来在位置i的位会移动到位置31 - i。例如最低位位置 0会变成最高位位置 31而最高位会变成最低位。复杂度目标题目期望的解应在O(1) 时间、O(1) 空间内完成——因为 32 是固定常数任何遍历全部 32 位的写法在渐进意义下都是常数时间位运算分治法则能把实际执行的运算次数从 32 次循环降到固定 5 条掩码操作。Hint 3 直接给出了最实用的构造式算法骨架初始化res 0遍历n的每一位用((n i) 1)提取位置i上的位若为 1则通过res | (1 (31 - i))将其放到结果中的对应位置。下面三种解法都是围绕这条核心观察展开的。2. 解法一暴力法字符串中转2.1 思路最直观的思路是用人脑的方式处理先把 32 位逐位读出来放进字符串反转字符串再根据反转后的字符串重建数值。这种方法易于理解但引入了 O(1) 但常数较大的额外空间一个长度 32 的字符串且两次循环 一次字符串反转代码更长。2.2 算法步骤初始化空字符串binary存放各位对位置i从 0 到 31用n (1 i)判断该位是否为 1把1或0追加到binary反转binary初始化res 0遍历反转后的字符串遇到1就用res | (1 i)置位返回res。2.3 多语言实现class Solution: def reverseBits(self, n: int) - int: binary for i in range(32): if n (1 i): binary 1 else: binary 0 res 0 for i, bit in enumerate(binary[::-1]): if bit 1: res | (1 i) return respublic class Solution { public int reverseBits(int n) { StringBuilder binary new StringBuilder(); for (int i 0; i 32; i) { if ((n (1 i)) ! 0) { binary.append(1); } else { binary.append(0); } } int res 0; String reversedBinary binary.reverse().toString(); for (int i 0; i 32; i) { if (reversedBinary.charAt(i) 1) { res | (1 i); } } return res; } }class Solution { public: uint32_t reverseBits(uint32_t n) { string binary ; for (int i 0; i 32; i) { if (n (1 i)) { binary 1; } else { binary 0; } } uint32_t res 0; for (int i 0; i 32; i) { if (binary[31 - i] 1) { res | (1 i); } } return res; } };class Solution { /** * param {number} n - a positive integer * return {number} - a positive integer */ reverseBits(n) { let binary ; for (let i 0; i 32; i) { if (n (1 i)) { binary 1; } else { binary 0; } } let res 0; for (let i 0; i 32; i) { if (binary[31 - i] 1) { res | 1 i; } } return res 0; } }public class Solution { public uint ReverseBits(uint n) { string binary ; for (int i 0; i 32; i) { if ((n (1 i)) ! 0) { binary 1; } else { binary 0; } } uint res 0; for (int i 0; i 32; i) { if (binary[31 - i] 1) { res | (1u i); } } return res; } }func reverseBits(n uint32) uint32 { binary : for i : 0; i 32; i { if n(1i) ! 0 { binary 1 } else { binary 0 } } var res uint32 0 for i, bit : range binary { if bit 1 { res | (1 (31 - i)) } } return res }class Solution { fun reverseBits(n: Int): Int { var binary for (i in 0 until 32) { binary if ((n and (1 shl i)) ! 0) 1 else 0 } var res 0 for ((i, bit) in binary.reversed().withIndex()) { if (bit 1) { res res or (1 shl i) } } return res } }class Solution { func reverseBits(_ n: Int) - Int { var binary for i in 0..32 { if (n (1 i)) ! 0 { binary 1 } else { binary 0 } } var res 0 for (i, bit) in binary.reversed().enumerated() { if bit 1 { res | (1 i) } } return res } }impl Solution { pub fn reverse_bits(n: u32) - u32 { let mut binary String::new(); for i in 0..32 { if n (1 i) ! 0 { binary.push(1); } else { binary.push(0); } } let mut res: u32 0; let reversed: Vecchar binary.chars().rev().collect(); for i in 0..32 { if reversed[i] 1 { res | 1 i; } } res } }2.4 复杂度分析时间复杂度O(1)——固定 32 位两次循环各 32 次迭代空间复杂度O(1)——字符串长度恒为 32不随输入规模增长。3. 解法二位运算逐位提取Hint 3 的标准实现3.1 思路暴力法中的字符串完全是多余的。既然反转的本质是把位置 i 的位搬到位置 31-i完全可以在整型上直接完成从最低位开始逐位取出放进结果的对应高位不需要任何中间存储。这正是 hints/reverse-bits.md Hint 3 描述的算法也是本仓库绝大多数语言实现所采用的主流写法。3.2 算法步骤初始化res 0对位置i从 0 到 31用(n i) 1提取n的第i位用bit (31 - i)把它移到结果中的镜像位置累加/按位或进res返回res。注意一个等价的常用写法循环 32 次每次res (res 1) | (n 1); n 1;——即把结果整体左移一位腾出最低位同时取出n当前最低位放入再右移n丢掉已处理的位。两者的数学本质完全一致本仓库的 c/0190-reverse-bits.c、java/0190-reverse-bits.java、javascript/0190-reverse-bits.js、cpp/0190-reverse-bits.cpp、rust/0190-reverse-bits.rs、typescript/0190-reverse-bits.ts、csharp/0190-reverse-bits.cs、kotlin/0190-reverse-bits.kt 均采用了这种边出边进的写法而 python/0190-reverse-bits.py、go/0190-reverse-bits.go、swift/0190-reverse-bits.swift、ruby/0190-reverse-bits.rb 采用直接定位 31-i的写法二者可互相印证。3.3 多语言实现class Solution: def reverseBits(self, n: int) - int: res 0 for i in range(32): bit (n i) 1 res (bit (31 - i)) return respublic class Solution { public int reverseBits(int n) { int res 0; for (int i 0; i 32; i) { int bit (n i) 1; res (bit (31 - i)); } return res; } }class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t res 0; for (int i 0; i 32; i) { uint32_t bit (n i) 1; res (bit (31 - i)); } return res; } };class Solution { /** * param {number} n - a positive integer * return {number} - a positive integer */ reverseBits(n) { let res 0; for (let i 0; i 32; i) { const bit (n i) 1; res bit (31 - i); } return res 0; } }public class Solution { public uint ReverseBits(uint n) { uint res 0; for (int i 0; i 32; i) { uint bit (n i) 1; res (bit (31 - i)); } return res; } }func reverseBits(n uint32) uint32 { var res uint32 0 for i : 0; i 32; i { bit : (n i) 1 res | (bit (31 - i)) } return res }class Solution { fun reverseBits(n: Int): Int { var res 0 for (i in 0 until 32) { val bit (n shr i) and 1 res res or (bit shl (31 - i)) } return res } }class Solution { func reverseBits(_ n: Int) - Int { var res 0 var num n for i in 0..32 { let bit (num i) 1 res | (bit (31 - i)) } return res } }impl Solution { pub fn reverse_bits(n: u32) - u32 { let mut res: u32 0; for i in 0..32 { let bit (n i) 1; res bit (31 - i); } res } }3.4 复杂度分析时间复杂度O(1)——固定 32 次迭代空间复杂度O(1)——仅一个结果变量无任何辅助存储。相比解法一这一版去掉了字符串分配、拼接与反转是零额外内存的干净实现。4. 解法三位运算分治掩码交换最优实现4.1 思路逐位循环每次只处理 1 个位一共 32 次。经典的分治技巧可以把这个过程压缩成固定 5 条掩码指令思路是由大到小地交换区块先交换左右各 16 位半个 32 位数再在每个 16 位块内交换左右各 8 位字节然后交换 4 位块半字节 nibble再交换 2 位块位对最后交换相邻 1 位。每一步都让所有位向最终镜像位置靠近一步。因为 32 2⁵恰好经过 5 层二分交换即可完成全部反转。这也是 articles/reverse-bits.md 中被称为Bit Manipulation (Optimal)的解法。4.2 算法步骤res n交换 16 位块res (res 16) | (res 16)交换 8 位块res ((res 0xff00ff00) 8) | ((res 0x00ff00ff) 8)交换 4 位块res ((res 0xf0f0f0f0) 4) | ((res 0x0f0f0f0f) 4)交换 2 位块res ((res 0xcccccccc) 2) | ((res 0x33333333) 2)交换 1 位块res ((res 0xaaaaaaaa) 1) | ((res 0x55555555) 1)用 0xFFFFFFFF或语言层面的无符号语义确保结果保持在 32 位内返回。各掩码含义0xff00ff00与0x00ff00ff分别选中每 16 位中的奇数/偶数 8 位块0xf0f0f0f0与0x0f0f0f0f选中 4 位块0xcccccccc与0x33333333选中 2 位块1100/0011交替0xaaaaaaaa与0x55555555选中单数/偶数位1010.../0101...。4.3 多语言实现class Solution: def reverseBits(self, n: int) - int: res n res (res 16) | (res 16) 0xFFFFFFFF res ((res 0xff00ff00) 8) | ((res 0x00ff00ff) 8) res ((res 0xf0f0f0f0) 4) | ((res 0x0f0f0f0f) 4) res ((res 0xcccccccc) 2) | ((res 0x33333333) 2) res ((res 0xaaaaaaaa) 1) | ((res 0x55555555) 1) return res 0xFFFFFFFFpublic class Solution { public int reverseBits(int n) { int ret n; ret ret 16 | ret 16; ret (ret 0xff00ff00) 8 | (ret 0x00ff00ff) 8; ret (ret 0xf0f0f0f0) 4 | (ret 0x0f0f0f0f) 4; ret (ret 0xcccccccc) 2 | (ret 0x33333333) 2; ret (ret 0xaaaaaaaa) 1 | (ret 0x55555555) 1; return ret; } }class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t ret n; ret (ret 16) | (ret 16); ret ((ret 0xff00ff00) 8) | ((ret 0x00ff00ff) 8); ret ((ret 0xf0f0f0f0) 4) | ((ret 0x0f0f0f0f) 4); ret ((ret 0xcccccccc) 2) | ((ret 0x33333333) 2); ret ((ret 0xaaaaaaaa) 1) | ((ret 0x55555555) 1); return ret; } };class Solution { /** * param {number} n - a positive integer * return {number} - a positive integer */ reverseBits(n) { let ret n 0; ret (ret 16) | (ret 16); ret ((ret 0xff00ff00) 8) | ((ret 0x00ff00ff) 8); ret ((ret 0xf0f0f0f0) 4) | ((ret 0x0f0f0f0f) 4); ret ((ret 0xcccccccc) 2) | ((ret 0x33333333) 2); ret ((ret 0xaaaaaaaa) 1) | ((ret 0x55555555) 1); return ret 0; } }public class Solution { public uint ReverseBits(uint n) { uint ret n; ret (ret 16) | (ret 16); ret ((ret 0xff00ff00) 8) | ((ret 0x00ff00ff) 8); ret ((ret 0xf0f0f0f0) 4) | ((ret 0x0f0f0f0f) 4); ret ((ret 0xcccccccc) 2) | ((ret 0x33333333) 2); ret ((ret 0xaaaaaaaa) 1) | ((ret 0x55555555) 1); return ret; } }func reverseBits(n uint32) uint32 { res : n res (res 16) | (res 16) res ((res 0xff00ff00) 8) | ((res 0x00ff00ff) 8) res ((res 0xf0f0f0f0) 4) | ((res 0x0f0f0f0f) 4) res ((res 0xcccccccc) 2) | ((res 0x33333333) 2) res ((res 0xaaaaaaaa) 1) | ((res 0x55555555) 1) return res }class Solution { fun reverseBits(n: Int): Int { var res n res (res ushr 16) or (res shl 16) res ((res and 0xff00ff00.toInt()) ushr 8) or ((res and 0x00ff00ff) shl 8) res ((res and 0xf0f0f0f0.toInt()) ushr 4) or ((res and 0x0f0f0f0f) shl 4) res ((res and 0xcccccccc.toInt()) ushr 2) or ((res and 0x33333333) shl 2) res ((res and 0xaaaaaaaa.toInt()) ushr 1) or ((res and 0x55555555) shl 1) return res } }class Solution { func reverseBits(_ n: Int) - Int { var res n res (res 16) | (res 16) 0xFFFFFFFF res ((res 0xff00ff00) 8) | ((res 0x00ff00ff) 8) res ((res 0xf0f0f0f0) 4) | ((res 0x0f0f0f0f) 4) res ((res 0xcccccccc) 2) | ((res 0x33333333) 2) res ((res 0xaaaaaaaa) 1) | ((res 0x55555555) 1) return res 0xFFFFFFFF } }impl Solution { pub fn reverse_bits(n: u32) - u32 { let mut ret n; ret (ret 16) | (ret 16); ret ((ret 0xff00ff00) 8) | ((ret 0x00ff00ff) 8); ret ((ret 0xf0f0f0f0) 4) | ((ret 0x0f0f0f0f) 4); ret ((ret 0xcccccccc) 2) | ((ret 0x33333333) 2); ret ((ret 0xaaaaaaaa) 1) | ((ret 0x55555555) 1); ret } }4.4 复杂度分析时间复杂度O(1)——恒定 5 条位运算指令与输入值无关空间复杂度O(1)——仅一个变量。三种解法在渐进复杂度上都是 O(1)但分治法的实际指令数最少约 5 次掩码交换 vs 32 次循环迭代且不依赖循环是面试中体现位运算功力的加分写法。5. 常见陷阱与语言差异5.1 有符号右移 vs 无符号右移在 Java、JavaScript 等语言中是有符号右移会保留符号位最高位为 1 时左侧补 1这会让反转结果出错必须使用无符号右移左侧恒补 0。可以在 javascript/0190-reverse-bits.js 与 java/0190-reverse-bits.java 的返回值处看到 0/ 无符号处理的痕迹分治版中 Java 的全部移位也都写成。而 C/C/Go/Rust 使用显式的无符号类型uint32_t/u32天然规避了符号扩展问题。5.2 硬编码错误的位宽题目明确规定 32 位因此循环必须完整执行 32 次前导零也必须参与反转。例如1反转后不是1而是0x80000000最高位为 1。无论是循环 31 次、提前剪枝还是用字符串法时把前导零丢掉都会得到错误答案。仓库中 kotlin/0190-reverse-bits.kt 对n 0做了提前返回优化但注意这只对全零输入安全不能推广为位数提前结束。5.3 语言级无符号语义Python 的整数是任意精度、移位后不会截断因此分治版 Python 需要在首尾显式 0xFFFFFFFF见上文解法三 Python 实现Swift 同理。C#/Go/C 使用uint/uint32_t类型则无需手动截断这解释了不同语言实现间细微的差异来源。6. 仓库中的完整实现索引本仓库为该题提供了 12 种语言的独立实现可作为交叉验证与语言差异学习的参考逐位边出边进写法c/0190-reverse-bits.c、cpp/0190-reverse-bits.cpp、java/0190-reverse-bits.java、javascript/0190-reverse-bits.js、typescript/0190-reverse-bits.ts、csharp/0190-reverse-bits.cs、rust/0190-reverse-bits.rs、kotlin/0190-reverse-bits.kt直接定位31 - i写法python/0190-reverse-bits.py、go/0190-reverse-bits.go、swift/0190-reverse-bits.swift、ruby/0190-reverse-bits.rb配套的完整题解含三种解法的 Intuition、Algorithm 与复杂度分析见 articles/reverse-bits.md渐进提示见 hints/reverse-bits.md。读者可通过对比同一算法在不同语言中的位运算符语法//ushr/shr、|/or、/and快速建立跨语言的位运算直觉。7. 小结反转 32 位整数本质上只有一条规律位置i的位搬到位置31 - i。围绕它三种解法由易到难层层递进解法核心手段时间空间亮点暴力法字符串中转O(1)O(1)思路直观适合入门位运算逐位(n i) 1bit (31 - i)O(1)O(1)零额外内存面试标准答案分治掩码16→8→4→2→1 位逐层交换O(1)O(1)固定 5 条指令性能最优掌握第二条Hint 3 的标准实现即可满分通过本题理解第三条的掩码设计则能同时迁移到位反转、字节交换、奇偶位重排等一系列位操作问题上。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
