Friday, March 21, 2014

Print binary representation of a decimal number

Problem
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”.
Solution
This is equivalent to implement toBinaryString() method built in Java API.

Lets think about the IEEE-754 standard. In a 32-bit machine, the 1st bit is for sign, 2nd – 9th digits are for exponent and the rest are for mantissa. Then you need to float the decimal point first and then determine the mantissa, etc. Way more complicated than I can handle…
Example

INPUT : 3.625
OUTPUT : 11.101


First you need to convert 3.625 into arithmetic binary (not how it's stored into a computer, it is different). I kind of do this in a strange way, but it's easy to understand. You already know 3 is represented in decimal as "11", but what is 0.625 in arithmetic binary?

First I take 0.625... can you subtract 1/2 without going negative? YES.
0.625-(1/2)=0.125
Next take 0.125 (the result from the above line)... can you subtract 1/4 without going negative? NO.
0.125-(1/4)=a negative number
Next take 0.125 again (the last positive result)... can you subtract 1/8 without going negative? YES.
0.125-(1/8)=0
We reached 0 so we stop. But we could keep going like this for 1/16, 1/32, 1/64, etc. Next, from top to bottom take all the YESes and replace them with 1s, and all the NOs and replace them with 0s to make up your binary number.
0.625-(1/2)=0.125 -- YES
0.125-(1/4)=negative -- NO
0.125-(1/8)=0 -- YES
So from top to bottom this would be "101". In other words, decimal 0.625 is represented in arithmetic binary as .101, and decimal 3.625 is represented as arithmetic binary 11.101.

Now how do you get that into what it looks like in a computer?
Use the steps in the tutorial:
1. Normalize the mantisa
11.101 --> 1.1101 x 2^1
2. Break it into parts:
sign: positive (0)
exponent: 1 + 127 = 128 (add 127 as explained in the tutorial), or 10000000 in binary.
mantissa: .1101 (note I dropped off the first 1 because it's redundant)

So the final number would be 0 10000000 11010000000000000000000
                                        (sign exponent mantissa)

Converting to Hex and Octal will depend on what you want to do. If you are wanting to do it how the computer does it, convert it to binary first and then convert it to hex or octal from there (hint: you can use Windows calculator to automatically convert binary numbers to Hex or Octal if you need). If you want just the arithmetic hex or octal, it can be done in similar ways to arithmetic binary.

Of course there are accuracy issues with floating point numbers.
Example 2 :
INPUT : 3.26
Output : ERROR

Code:

public static String printBinary(String n) {
    int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
    double decPart = Double.parseDouble(n.substring(n.indexOf('.'),
            n.length()));
    String int_string = "";
    while (intPart > 0) {
        int r = intPart % 2;
        intPart >>= 1;
        int_string = r + int_string;
    }
    StringBuffer dec_string = new StringBuffer();
    while (decPart > 0) {
        if (dec_string.length() > 32)
            return "ERROR";
        if (decPart == 1) {
            dec_string.append((int) decPart);
            break;
        }
        double r = decPart * 2;
        if (r >= 1) {
            dec_string.append(1);
            decPart = r - 1;
        } else {
            dec_string.append(0);
            decPart = r;
        }
    }
    return int_string + "." + dec_string.toString();
}

TC - O(n) , n = length of number e.g digits in number
SC - O(1)

Dry running the code 
First we get the integer or exponent part of the decimal string. We divide the integer until we get 0.

Now we get the decimal part. We multiply decimal part by 2, and if it is greater than 1, we append 1 to decimal string, else we add 0. We continue this, until decimal part becomes 0.
eg. 0.25 * 2 > 1 false implies 0
0.5 * 2 = 1 >= 1 true


2 comments:

  1. intPart >>= 1; this is fr wat?

    ReplyDelete
    Replies
    1. Hi Chaitrali, sorry for the delayed response. This means division by 2.
      In general, bit_arg>>shift_arg shifts bits to of bit_arg shift_arg places to the right -- equivalent to integer division by 2^shift_arg

      Delete