Binary Representation

Binary Representation

---

今天还是一道有关数学计算的题目，Binary Representation，来自LintCode，难度为Hard， Acceptance为19%。

这类题目不涉及太多的数据结构和算法，更多的是考察基础知识的运用。

题目如下

Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return ERROR.
Example
For n = "3.72", return "ERROR".
For n = "3.5", return "11.1".

思路如下

---

小数的二进制表示法

首先，这个的输入是小数，这里就设计到小数的二进制表示法。整数部分表示成二进制相信大家都会，只要不断的对2取余，然后再将余数反转就可以。

那么小数部分如何表示成二进制，方法如下：

对十进制小数乘2，得到的整数部分和小数部分，整数部分既是相应的二进制数码，再用2乘小数部分(之前乘后得到新的小数部分)，又得到整数和小数部分。如此不断重复，直到小数部分为0或达到精度要求为止。第一次所得到为最高位，最后一次得到为最低位如：0.25的二进制0.25*2=0.5 取整是0。0.5*2=1.0 取整是1即0.25的二进制为 0.01 ( 第一次所得到为最高位，最后一次得到为最低位)。例子如下：
0.8125的二进制
0.8125*2=1.625 取整是1
0.625*2=1.25 取整是1
0.25*2=0.5 取整是0
0.5*2=1.0 取整是1
即0.8125的二进制是0.1101（第一次所得到为最高位,最后一次得到为最低位）

精度

在上述的计算方法中，可能出现无限循环的情况，因此必须控制精度。题目中已经给出32位小数精度，超过则返回ERROR。

那么在代码中如何检查是否达到精度要求或者已经进入循环呢。

方法一：只检查是否达到精度，即只检查小数部分是否已经超过32位，超过则返回ERROR。
方法二：检查计算精度，同时用一个Set记录每次计算得到的小数部分，在下一次计算之前检查这个Set中是否出现了同一个数字，是则说明出现了循环，此时不论是否达到精度，都应该返回ERROR（因为即使此时还没达到精度要求，在后续的计算中一定会超过精度要求）。

代码如下

---

方法一

public class Solution {
    /**
     *@param n: Given a decimal number that is passed in as a string
     *@return: A string
     */
    private String parseInteger(String str) {
        int n = Integer.parseInt(str);
        if (str.equals("") || str.equals("0")) {
            return "0";
        }
        String binary = "";
        while (n != 0) {
            binary = Integer.toString(n % 2) + binary;
            n = n / 2;
        }
        return binary;
    }
    
    private String parseFloat(String str) {
        double d = Double.parseDouble("0." + str);
        String binary = "";
        int count = 0;
        while (d > 0) {
            count++;
            if(count > 32)
                return "ERROR";
            d = d * 2;
            if (d >= 1) {
                binary = binary + "1";
                d = d - 1;
            } else {
                binary = binary + "0";
            }
        }
        return binary;
    }
    
    public String binaryRepresentation(String n) {
        if (n.indexOf('.') == -1) {
            return parseInteger(n);
        }
        String[] params = n.split("\\.");
        String flt = parseFloat(params[1]);
        if (flt == "ERROR") {
            return flt;
        }
        if (flt.equals("0") || flt.equals("")) {
            return parseInteger(params[0]);
        }
        return parseInteger(params[0]) + "." + flt;
    }
}

方法二

public class Solution {
    /**
     *@param n: Given a decimal number that is passed in as a string
     *@return: A string
     */
    private String parseInteger(String str) {
        int n = Integer.parseInt(str);
        if (str.equals("") || str.equals("0")) {
            return "0";
        }
        String binary = "";
        while (n != 0) {
            binary = Integer.toString(n % 2) + binary;
            n = n / 2;
        }
        return binary;
    }
    
    private String parseFloat(String str) {
        double d = Double.parseDouble("0." + str);
        String binary = "";
        HashSet<Double> set = new HashSet<Double>();
        while (d > 0) {
            if (binary.length() > 32 || set.contains(d)) {
                return "ERROR";
            }
            set.add(d);
            d = d * 2;
            if (d >= 1) {
                binary = binary + "1";
                d = d - 1;
            } else {
                binary = binary + "0";
            }
        }
        return binary;
    }
    
    public String binaryRepresentation(String n) {
        if (n.indexOf('.') == -1) {
            return parseInteger(n);
        }
        String[] params = n.split("\\.");
        String flt = parseFloat(params[1]);
        if (flt == "ERROR") {
            return flt;
        }
        if (flt.equals("0") || flt.equals("")) {
            return parseInteger(params[0]);
        }
        return parseInteger(params[0]) + "." + flt;
    }
}