Leetcode.面试题 05.02 二进制数转字符串

题目链接

面试题 05.02 二进制数转字符串 Mid

题目描述

二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。

示例1:

输入：0.625
输出：“0.101”

示例2:

输入：0.1
输出：“ERROR”
提示：0.1无法被二进制准确表示

提示：

• 32位包括输出中的 "0."这两位。
• 题目保证输入用例的小数位数最多只有 6 位

分析：

• $0.1=2^{-1}=\frac{1}{2}=0.5$
• $0.01=2^{-2}=\frac{1}{4}=0.25$
• $0.001=2^{-3}=\frac{1}{8}=0.125$
• …

我们再看 小数点后 有几位二进制数 能表示的十进制数：

• 一位，$0.1=0.5$
• 两位，$0.11=0.75$
• 三位，$0.111=0.875$
• 四位，$0.1111=0.9375$
• 五位，$0.11111=0.96875$
• 六位，$0.111111=0.984375$
• 七位，$0.1111111=0.9921875$
• …

我们发现，当小数点后面有六位二进制数时，它就能表示十进制的六位小数了（因为题目输入的小数，最多小数点后面六位）。

所以我们实际上，只需要计算小数点后六位二进制数能否表示，题目输入的小数即可。

时间复杂度：$O(1)$

C++代码：

class Solution {
public:string printBin(double num) {int i = 1;string s = "0.";//当 num == 0 或者 已经遍历到第七位数时 退出循环while(num > 0 && i <= 6){//t 就是 1 / (2 ^ i)double t = 1.0 / (1 << i);if(num >= t){num -= t;s += "1";}else s += "0";i++;}//最后如果 num == 0 说明，num 能被六位二进制数表示出来if(num == 0) return s;else return "ERROR";}
};

Java代码：

class Solution {public String printBin(double num) {int i = 1;StringBuilder sb = new StringBuilder("0.");while(num > 0 && i <= 6){double t = 1.0 / (1 << i);if(num >= t){sb.append('1');num -= t;}else sb.append('0');i++;}if(num == 0) return sb.toString();else return "ERROR";}
}