LeetCode 面试题 05.02. 二进制数转字符串
目录
题目描述
题意分析
给一个介于 0 和 1 之间的实数，输出它的二进制表示，形如
0.101。如果这个数无法用 32 个及以内的字符精确表示，就返回字符串ERROR。输入被限定在开区间
(0, 1)，所以整数部分恒为 0，要处理的只有小数部分——这把问题从「进制转换」窄化成了「纯小数的进制展开」，不需要考虑整数位与符号。「32 个字符」这条限制要算清楚：输出必然以
0.开头，占掉 2 个字符，因此小数点后最多允许 30 位二进制。换句话说，展开超过 30 位还没结束，就该判定为无法表示。这条限制同时也是循环的天然上界，保证程序不会因为无限展开而死循环。「精确表示」是个数学判定而非近似判定：一个二进制小数有限的充要条件是它可以写成
k / 2^m的形式。像0.625 = 5 / 8可以，0.1就不行，后者在二进制下是无限循环小数，必然触发ERROR。边界：输入不会是 0 或 1（开区间），所以不存在只输出
0.的情形；恰好用满 30 位的数应当正常输出而不是报错；第一位就结束的数（如 0.5）输出0.1。
解法：位运算压缩状态
核心思路
十进制小数转二进制的标准手法是「乘二取整」：把小数反复乘以 2，每次取走整数部分作为下一位，剩下的小数部分继续。它的正确性来自位权定义——若
num = 0.b₁b₂b₃…（二进制），那么num × 2 = b₁.b₂b₃…，乘一次就把最高位顶到了整数位上，减掉它之后剩下的正是去掉首位后的小数。所以每一轮做三件事：
num *= 2；若结果不小于 1 则该位是 1，追加字符并把num减去 1；否则该位是 0，只追加字符。循环的不变量是「num始终等于尚未输出的那部分小数，且它恒在[0, 1)内」。当num变成 0，说明所有位都已输出，展开结束。终止有两个出口。正常出口是
num归零；异常出口是长度超限——每轮开头先检查已生成的字符数，达到 32 还需要继续，说明剩下的部分放不进去了，直接返回ERROR。把长度检查放在循环开头而不是结尾，是为了在「刚好写满 32 个字符且恰好结束」时不误报。这里有个容易被忽略但值得一提的性质：整个过程在浮点数上是精确的，不存在误差累积。乘以 2 只是把双精度数的指数加一，尾数一位不动；
num不小于 1 时减去 1 也是精确可表示的运算。因此不需要设置任何eps容差，num > 0与num >= 1都可以放心地用严格比较。
解题步骤
- 初始化输出：从
"0."开始拼接。整数部分恒为 0 是输入区间给的，不需要计算。- 循环条件用
num > 0：num归零即表示展开完毕。不要写成固定 30 次循环，那样会给有限小数补上一串多余的 0。- 进循环先查长度：
if (answer.length() >= 32) return "ERROR";。此时已有 32 个字符而num仍大于 0，说明还需要更多位，必然超限。放在循环开头是关键——若放在追加之后再判断，恰好用满 32 个字符的合法输入会被误判成错误。- 乘二取位：
num *= 2之后，num >= 1说明这一位是 1，追加'1'并num -= 1；否则追加'0'。减 1 这一步不能漏，它对应「取走整数部分」，漏掉会让后续所有位全错。- 返回：循环自然退出时
num为 0，拼好的字符串就是答案。以
num = 0.625走一遍。初始answer = "0."，长度 2。第一轮：长度 2 未超限；
num变成 1.25，不小于 1，追加'1'并减 1 得 0.25，此时answer = "0.1"。第二轮：num变成 0.5，小于 1，追加'0'，answer = "0.10"。第三轮：num变成 1.0，不小于 1，追加'1'并减 1 得 0，answer = "0.101"。第四轮的循环条件num > 0不成立，退出，返回0.101。验证一下：0.101二进制等于1/2 + 0/4 + 1/8 = 0.625，正确。再看
num = 0.1。它等于1/10，分母含有质因数 5，无法写成k / 2^m，二进制下是无限循环的0.0001100110011…。循环会一直追加字符，直到某一轮开头检测到长度已达 32 而num仍大于 0，返回ERROR。
代码实现
class Solution {
public String printBin(double num) {
StringBuilder answer = new StringBuilder("0.");
while (num > 0) {
// 长度检查放在追加之前，恰好写满 32 位的合法输入才不会被误判。
if (answer.length() >= 32) {
return "ERROR";
}
num *= 2;
if (num >= 1) {
answer.append('1');
num -= 1;
} else {
answer.append('0');
}
}
return answer.toString();
}
}
func printBin(num float64) string {
answer := []byte{'0', '.'}
for num > 0 {
// 长度检查放在追加之前，恰好写满 32 位的合法输入才不会被误判。
if len(answer) >= 32 {
return "ERROR"
}
num *= 2
if num >= 1 {
answer = append(answer, '1')
num -= 1
} else {
answer = append(answer, '0')
}
}
return string(answer)
}
复杂度分析
- 时间复杂度：$O(1)$，循环次数被 32 个字符的上限卡死，最多迭代 30 轮，每轮只有一次乘法、一次比较和一次字符追加。
- 空间复杂度：$O(1)$，输出缓冲区长度不超过 32 个字符，除此之外只有一个浮点变量。
关键点总结
- 小数转进制用「乘基取整」，整数转进制用「除基取余」，两者方向相反；能说清「乘 2 是把最高位顶到整数位」这个位权解释，比记住口诀更能应对追问。
- 这里的浮点运算是精确的：乘 2 只改指数、减 1 在
[1, 2)区间内可精确表示，所以不需要eps容差；面试中主动指出这一点，能打消考官对浮点误差的顾虑。- 长度检查必须放在追加之前，这是「恰好用满上限」这类边界的通用处理位置；写在后面会把合法的极限用例判成错误。
- 一个纯小数二进制有限的充要条件是它形如
k / 2^m，分母含 2 以外的质因数就必然无限循环——这是判定ERROR的数学依据，也是面试官期待你说出来的一句话。- 循环终止依赖
num归零而不是固定轮数，能让有限小数在恰当的位数处停下，不补多余的 0。- 面试常见追问是「不用浮点怎么做」：可以把输入乘以某个 2 的幂化成整数运算，或者按分数形式做长除；能提一句替代路径，说明你理解算法而不只是背模板。
易错点总结
- 长度检查放在追加之后：恰好需要 30 位小数的输入 → 写完最后一位时长度正好 32，随即被判成
ERROR，而它本该正常输出。- 上限写成 30 或 33：
num = 0.5这类短输出不受影响，但写成> 32时，需要 31 位的非法输入会多输出一位才报错，返回长度 33 的字符串。- 忘记
num -= 1：num = 0.625→ 第一轮取到 1 后num仍是 1.25，之后每轮都不小于 1，输出变成一长串 1 并最终误报ERROR。- 循环条件写成
num >= 0：num = 0.5→num归零后仍继续循环，不断追加'0'直到触发长度上限，把有限小数误判成ERROR。- 判定写成
num > 1：num = 0.5→ 第一轮num恰好等于 1，被当成 0 位，输出0.0且num未减，随后死循环到超限报错。- 给浮点比较加容差：
num = 0.5时若写成num >= 1 - 1e-9，某些本应为 0 的位会被当成 1，得到偏大的结果；本题的乘减运算精确，容差只会引入错误。- 固定循环 30 次不提前退出：
num = 0.5→ 输出0.1后继续补 29 个 0，字符串虽在长度限内但与期望输出不符。- 初始串写成
"0"漏掉小数点：num = 0.5→ 输出01，格式错误；小数点也占一个字符，漏掉会连带把长度上限算错。- 在 Java 里用字符串拼接而非
StringBuilder：功能上仍对，但每轮生成新对象；面试中被追问时说不出「可变缓冲区避免重复拷贝」会显得基础不牢。- 误以为要处理整数部分或负数：输入被限定在开区间
(0, 1)，额外加的符号与整数分支是死代码，反而会掩盖真正的边界判断。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 166. 分数到小数 | 中等 | 同为小数展开，但要用哈希表记录余数位置以识别循环节并加括号 |
| 405. 数字转换为十六进制数 | 简单 | 整数方向的进制转换，靠四位一组取掩码，负数按补码处理 |
| 168. Excel 表列名称 | 简单 | 除基取余的典型题，难点是这套编号从 1 开始需要先减一 |
| 面试题 05.01. 插入 | 简单 | 同属位运算基础题，操作对象是整数的固定区间而非小数展开 |
| 面试题 05.06. 整数转换 | 简单 | 关注两数的二进制差异位数，不涉及字符串输出 |