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

Examples

Example 1:

Input: num = 3.625
Output: 11.101

Example 2:

Input: num = 3.26
Output: ERROR
Explanation: There are accuracy issues with floating point numbers.

Read more: accuracy issues with floating point numbers.

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…

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. => 1 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 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. =>1 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 mantissa: 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.

Code

Java
public 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();
}

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

Complexity

  • ⏰ Time complexity: O(n) where n is length of number e.g digits in number
  • 🧺 Space complexity: O(1)