Cracking the coding interview--Q5.2

Hawstein | January 2, 2013

题目

原文:

Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation.If the number can not be represented accurately in binary, print “ERROR”.

译文:

给定一个字符串类型(string)表示的小数,打印出它的二进制表示。 如果这个数无法精确地表示为二进制形式,输出”ERROR”。

解答

整数部分通过不断地对2取余然后除以2来得到其二进制表示, 或是不断地和1按位与然后除以2得到其二进制表示。 小数部分则通过不断地乘以2然后与1比较来得到其二进制表示。 小数部分转化为二进制,通过乘以2然后与1比较,大于等于1则该位为1,并且该值减去1; 否则该位为0。不断地通过这种操作最终能使该小数部分的值变为0的,即可精确表示。 否则将无法用有限的位数来表示这个小数部分。我们可以设定一个长度,比如说32, 在32位之内还无法精确地表示这个小数部分的,我们就认为它无法精确表示了。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

string print_binary(string val){
    int pos = val.find('.', 0);
    int intpart = atoi(val.substr(0, pos).c_str());
    double decpart = atof(val.substr(pos, val.length()-pos).c_str());
    string intstr = "", decstr = "";
    while(intpart > 0){
        if(intpart&1) intstr = "1" + intstr;
        else intstr = "0" + intstr;
        intpart >>= 1;
    }
    while(decpart > 0){
        if(decstr.length() > 32) return "ERROR";
        decpart *= 2;
        if(decpart >= 1){
            decstr += "1";
            decpart -= 1;
        }
        else
            decstr += "0";
    }
    return intstr + "." + decstr;
}
int main(){
    string val = "19.25";
    cout<<print_binary(val)<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview

声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处
出处:http://hawstein.com/2013/01/02/5.2/