Print binary representation of a decimal number

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

My initial thoughts:
I thought this question ask me to implement toBinaryString() method built in Java API. So I was thinking 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…
Turns out the question asks for something like this:
INPUT: 3.25
OUTPUT 11.01
i.e., we treat the integer and decimal parts separately.

My initial codes:

	public static String toBinary(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 digit = intPart % 2;
			intPart = intPart >> 1; // divide by 2
			int_string += digit;
		}

		String dec_string = new String();
		Set<Double> seen = new HashSet<Double>();
		seen.add(decPart);
		while (decPart != 0.0) {
			System.out.println("decPart = " + decPart);
			int digit = decPart * 2 >= 1 ? 1 : 0;
			decPart = decPart * 2 >= 1 ? decPart * 2 - 1 : decPart * 2;
			if (seen.contains(decPart)) {
				return "ERROR";
			} else {
				seen.add(decPart);
			}
			dec_string += digit;
		}

		return int_string + "." + dec_string;
	}

Comments after running:
It tries to represent decimals that cannot be represented in finite binary bits by keeping adding digits, only to find that it hits the bottom line of the machine precision and then round off.
INPUT: 3.126
EXPECTED OUTPUT: ERROR
OUTPUT: 11.00100000010000011000100100110111010010111100011010101

Solution:

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

The solution controls the limit of the representation by saying that if after 32 bits the number still cannot be fully represented (hits 1 after some times of multiplications), then it will reprot error.

Advertisements

Set all bits of a number in a range equal to another number

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100

My initial thoughts:

  1. Create a mask with 1s but only 0s between positions i and j. AND the mask with N to clear the bits between i and j to 0s.
  2. Create another mask with 0s but only 1s between positions i and j. AND the mask with M to clear the bits outside i and j to 0s.
  3. OR N and M.

My initial codes:

	public static void setBits(int N, int M, int i, int j) {
		int mask = 1;
		for (int digit = i; digit <= j; ++digit)
			mask |= (mask << digit);
		N &= ~mask;
		M &= mask;
		N = N | M;
	}

Comments after running:
It does not work…

Solution:

	public static int updateBits(int n, int m, int i, int j) {
		int max = ~0; /* All 1's */

		// 1's through position j, then 0's
		int left = max - ((1 << j) - 1);

		// 1's after position i
		int right = ((1 << i) - 1);

		// 1's with 0s between i and j
		int mask = left | right;

		// Clear i through j, then put m in there
		return (n & mask) | (m << i);
	}

The idea is the same as mine but my implementation is wrong…

Next Newer Entries