Lintcode: Binary Representation

Lintcode: Binary Representation - neverlandly - 博客园

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".

For int part, similar approach of extracting numbers from int:

1. use %2 to get each digit from lowest bit to highest bit.

2. int right shift 1 position (=>>1).

3. construct the binary number (always add to the higher position of the current binary number)

Please refer to the code below for the process above.

For decimal part, use *2 approach.  For example:

int n = 0.75

n*2 = 1.5

Therefore, the first digit of binary number after '.' is 1 (i.e. 0.1).  After constructed the first digit, n= n*2-1

http://www.jiuzhang.com/solutions/binary-representation/

    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;
    }

https://codesolutiony.wordpress.com/2015/04/30/lintcode-binary-representation/

public String binaryRepresentation(String n) {

        if (n == null || n.length() == 0) {

            return n;

        }

        String[] parts = n.split("\\.");

        StringBuilder sb = new StringBuilder();

        int first = Integer.parseInt(parts[0]);

        boolean isNeg = first < 0;

        if (first == Integer.MIN_VALUE) {

            for (int i = 0; i < 32; i++) {

                sb.append("1");

            }

        } else {

            first = Math.abs(first);

            while (first != 0) {

                sb.insert(0, first & 1);

                first >>= 1;

            }

        }

        if (sb.length() == 0) {

            sb.append("0");

        }

        //handle the decimal part

        if (parts.length == 2 && Long.parseLong(parts[1]) != 0) {

            sb.append(".");

            BigDecimal value = new BigDecimal("0." + parts[1]);

            Set<BigDecimal> store = new HashSet<BigDecimal>();

            while (value.compareTo(BigDecimal.ZERO) > 0) {

                if (sb.substring(sb.indexOf(".") +1).length() > 32 || store.contains(value))  {

                    return "ERROR";

                }

                store.add(value);

                System.out.println(value);

                if (value.compareTo(new BigDecimal(0.5)) >= 0) {

                    sb.append("1");

                    value = value.multiply(BigDecimal.valueOf(2)).subtract(BigDecimal.ONE);

                } else {

                    sb.append("0");

                    value = value.multiply(BigDecimal.valueOf(2));

                }

            }

        }

        if (isNeg == true) {

            sb.insert(0, "-");

        }

        return sb.toString();

    }

    public String binaryRepresentation(String n) {
 7         int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
 8         double decPart = Double.parseDouble(n.substring(n.indexOf('.')));
 9         String intstr = "";
10         String decstr = "";
11         
12         if (intPart == 0) intstr += '0';
13         while (intPart > 0) {
14             int c = intPart % 2;
15             intstr = c + intstr;
16             intPart = intPart / 2;
17         }
18        
19         while (decPart > 0.0) {
20             if (decstr.length() > 32) return "ERROR";
21             double r = decPart * 2;
22             if (r >= 1.0) {
23                 decstr += '1';
24                 decPart = r - 1.0;
25             }
26             else {
27                 decstr += '0';
28                 decPart = r;
29             }
30         }
31         return decstr.length() > 0? intstr + "." + decstr : intstr;
32     }
33 }

http://www.javawithus.com/programs/decimal-to-binary
   public String toBinary(int n) {
       if (n == 0) {
           return "0";
       }
       String binary = "";
       while (n > 0) {
           int rem = n % 2;
           binary = rem + binary;
           n = n / 2;
       }
       return binary;
   }
JDK code:
public static String toBinaryString(int i) {
return toUnsignedString0(i, 1);
}
private static String toUnsignedString0(int val, int shift) {
    // assert shift > 0 && shift <=5 : "Illegal shift value";
    int mag = Integer.SIZE - Integer.numberOfLeadingZeros(val);
    int chars = Math.max(((mag + (shift - 1)) / shift), 1);
    char[] buf = new char[chars];

    formatUnsignedInt(val, shift, buf, 0, chars);

    // Use special constructor which takes over "buf".
    return new String(buf, true);
}

/**
 * Format a long (treated as unsigned) into a character buffer.
 * @param val the unsigned int to format
 * @param shift the log2 of the base to format in (4 for hex, 3 for octal, 1 for binary)
 * @param buf the character buffer to write to
 * @param offset the offset in the destination buffer to start at
 * @param len the number of characters to write
 * @return the lowest character  location used
 */
 static int formatUnsignedInt(int val, int shift, char[] buf, int offset, int len) {
    int charPos = len;
    int radix = 1 << shift;
    int mask = radix - 1;
    do {
        buf[offset + --charPos] = Integer.digits[val & mask];
        val >>>= shift;
    } while (val != 0 && charPos > 0);

    return charPos;
}
    /**
     * All possible chars for representing a number as a String
     */
    final static char[] digits = {
        '0' , '1' , '2' , '3' , '4' , '5' ,
        '6' , '7' , '8' , '9' , 'a' , 'b' ,
        'c' , 'd' , 'e' , 'f' , 'g' , 'h' ,
        'i' , 'j' , 'k' , 'l' , 'm' , 'n' ,
        'o' , 'p' , 'q' , 'r' , 's' , 't' ,
        'u' , 'v' , 'w' , 'x' , 'y' , 'z'
    };
Read full article from Lintcode: Binary Representation - neverlandly - 博客园