Algorithm

LintCode/Binary Representation

Problem Summary

Given a decimal number that is passed in as a string, return the binary representation (also a string). If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return ERROR.

Solution

We need to transfer the integrel part and the fractional part of the given number into binary representation, but they need to be processed in different methods.

Be careful about these cases:
    1. The integral or frational part is 0.
    2. The fractional part has some ending zeros.

Code

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstring>
using namespace std;
class Solution {
public:
    /*
     * @param n: Given a decimal number that is passed in as a string
     * @return: A string
     */
    string binaryRepresentation(string &n) {
    	int len = n.length();
    	int pos = n.find('.');
    	if (pos == string::npos)
    		pos = len;
    	string integral,fractional;
    	long long weight = 5, sum = 0;
    	int i = 1;
    	while (i<33 && pos+i<len) {
    		sum = 10*sum + n[pos+i] - '0';
    		if (sum >= weight) {
    			while (sum >= weight) {
    				sum -= weight;
    				fractional+='1';
    				weight *= 5;
    			}
    		}
    		else {
    			weight *= 5;
    			fractional+='0';
    		}
    		++i;
    	}
    	if (sum > 0)
 			return "ERROR";
    	while (pos+i<len) {
    		sum = 10*sum + n[pos+i] - '0';
    		if (sum > 0)
 				return "ERROR";
    		++i;
    	}
    	sum = 0;
    	i = 0;
    	while (i<pos) {
    		sum = 10*sum + n[i] - '0';
    		++i;
    	}
    	weight = 1;
    	for (int j = 0; sum>0 ; ++j)
    	{
    		if (weight & sum) {
    			sum -= weight;
    			integral = '1' + integral;
    		}
    		else
    			integral = '0' + integral;
    		weight <<= 1;
    	}
    	bool zero = true;
    	for (int j = 0; j<fractional.length(); j++)
    		if (fractional[j] != '0') {
    			zero = false;
    			break;
    		}
    	if(!zero)
    		while (fractional.length()>0 && fractional[fractional.length()-1]=='0')
    			fractional.erase(fractional.length()-1);
    	if (integral.length()==0)
    			integral = "0";
    		
    	if (zero)
    		return integral;
    	else
    		return integral + '.' + fractional;
    }
};
int main(int argc, char const *argv[])
{
	Solution s;
	string n("0.0");
	cout<<s.binaryRepresentation(n)<<endl;
	return 0;
}