Cracking the Coding Interview 5.2

Chapter 5 is all about bit manipulation. I'll be working with JS. Here's the puzzle:

Given a real number between 0 and 1 (e.g. 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR".

My first thought is that this requires knowledge of binary representation of decimals which is something like twos compliment. Off to do some googling!

...

So I found that it's similar to powers of two where each position is represented by 2^n where n is the position, but it's sort of reversed and 1/2^n.

So 0.75 would be 1/2^1 + 1/2^2 = 1/2 + 1/4 = 0.11

For this problem I can't just say input.toString(2) because I need to check if it can be represented in 32 bits.

What does it mean to be represented in 32 bits? It means if I get to 0.111011...10 to the 32nd position and still have remainder, then it cannot be represented completely.

First pass algorithm

First I'm going to try this basic pattern:

1. Subtract 1/2^n from the input
2. If the result is negative, keep n position a zero
3. If the result is positive, make n position a 1
4. Move to the next position
5. Check if we still have a remainder
   • If yes, check if we're at position 32, possibly error

This should work fine when zero is the input because the first round will come up negative and there will be no remainder.

Here's my quick first pass that seems to work:

const decimalToBinary = (dec, pos = 1, result = []) => {
  const sub = 1 / 2 ** pos;
  let next = dec - sub;
  let binaryPosition = 1;
  if (next < 0) {
    binaryPosition = 0;
    next = dec;
  }
  result.push(binaryPosition);

  // check exit conditions
  if (next === 0) {
    return result.join('');
  } else if (pos === 32) {
    return 'ERROR';
  }
  return decimalToBinary(next, pos + 1, result);
};

console.log(decimalToBinary(0.75));
console.log(decimalToBinary(0.25));

I might add a check at the beginning that the input is as intended (between 0 and 1). I'm also not sure how to find valid and invalid decimal input, all random decimals I tried return ERROR - which is probably accurate.

Time to read the book solution!

The book starts with a slightly different algorithm:

0b0.101 = 1 * 1/2 + 0 * 1/2^2 + 1 * 1/2^3

But this is equivalent to my algorithm. But this is where the similarities end. In the book they use an iterative (vs recursive) approach which multiplies the number by 2 and checking if it's gone over 1. If it is, the binary is a 1 for the position, otherwise it's a zero.

This is similar but multiplying by 2 instead of subtracting the 1/2^n (essentially division with remainder). It's interesting that they multiply by two instead of bit shifting by 1 (num << 1).

Here's my implementation in JS of their solution:

const printBinary = (num) => {
  if (num >= 1 || num <= 0) {
    return 'ERROR';
  }

  let binary = '';
  while (num > 0) {
    if (binary.length >= 32) {
      return 'ERROR';
    }

    const twoNum = num * 2;
    if (twoNum >= 1) {
      binary = binary + '1';
      num = twoNum - 1;
    } else {
      binary = binary + '0';
      num = twoNum;
    }
  }
  return binary;
};

While the BigO of the solutions is the same, the recursive in JS will have some overhead of function calls. Since we know the max calls will be 32 it's not a concern, so the biggest question is which is easier to comprehend. I think my solution keeps closer to the mathematical solutions which is the logical way most people will approach understanding this problem. If we did need this function to be hyper-optimized, we may need to take a closer look at the individual operations of each pattern and take the one with the fewest cycles.

This was pretty fun, see you in the next one!