Find Shortest Binary String In Given Interval

Question

Say I have two values 0 <= a < b <= 1, how can I chose an x such that a <= x<b with the shortest binary expansion possible?

My approach so far is to take the binary strings of a and b, with the decimal point removed, and at the first place they differ, take the expansion of a up until that point. If there's more of a to consume, strip the last bit. Finally, add 1.

In JavaScript:

var binaryInInterval = function(a, b) {
  if (a < 0 || b > 1 || a >= b) return undefined;

  var i, u, v, x = '';

  a = a.toString(2).replace('.', '');
  b = b.toString(2).replace('.', '');

  for (i = 0; i < Math.max(a.length, b.length); i++) {
    u = parseInt(a.substr(i, 1), 10) || 0;
    v = parseInt(b.substr(i, 1), 10) || 0;

    x += u.toString();
    if (u != v) { 
      if (i + 1 < a.length) x = x.slice(0, -1);
      x += '1';
      break;
    }
  }

  return '0.' + x.substr(1);
};

This works, but I'm not convinced that it's generally correct. Any thoughts?...

---

EDIT I've already found a case that doesn't work correctly :P

binaryInInterval(0.25, 0.5) = '0.1'

0.25  0.01
0.5   0.1
        ^ Difference
          but a hasn't been fully consumed
          so we strip 00 to 0 before adding 1

---

EDIT 2 An alternative algorithm would be to iterate through 2^-n and check if any multiple of this fits within the interval. This would be more expensive, however.

Answer 1

It will fail for inputs like a = 0.1, b = 0.100001 (in binary -- i.e. a = 0.5, b = 0.515625 in decimal). The correct answer would be 0.1 in this case, but your algorithm will produce 0.11 instead, which is not only not minimal-length, but greater than b :-(

Your digit-checking looks fine to me -- the problem is that when you have made the (right) decision to end the loop, you construct the wrong output if b's digit string is longer. One easy way to fix it would be to output digits one-at-a-time, as you go along: until you see a different character, you know you must include the current character.

One more tip: I don't know Javascript well, but I think both parseInt() calls are unnecessary, since nothing you do with u or v actually requires arithmetic.

[EDIT]

Here is some example digit-at-a-time code that incorporates a few other considerations:

var binaryInInterval = function(a, b) {
  if (a < 0 || b > 1 || a >= b) return undefined;

  if (a == 0) return '0';  // Special: only number that can end with a 0

  var i, j, u, v, x = '';

  a = a.toString(2).replace('.', '');
  b = b.toString(2).replace('.', '');

  for (i = 0; i < Math.min(a.length, b.length); i++) {
    u = a.substr(i, 1);
    v = b.substr(i, 1);

    if (u != v) {
      // We know that u must be '0' and v must be '1'.
      // We therefore also know that u must have at least 1 more '1' digit,
      // since you cannot have a '0' as the last digit.
      if (i < b.length - 1) {
        // b has more digits, meaning it must
        // have more '1' digits, meaning it must be larger than
        // x if we add a '1' here, so it's safe to do that and stop.
        x += '1';     // This is >= a, because we know u = '0'.
      } else {
        // To ensure x is >= a, we need to look for the first
        // '0' in a from this point on, change it to a '1',
        // and stop.  If a only contains '1's from here on out,
        // it suffices to copy them, and not bother appending a '1'.
        x += '0';
        for (j = i + 1; j < a.length; ++j) {
          if (a.substr(j, 1) == '0') {
            break;
          }
        }
      }
      break;  // We're done.  Fall through to fix the binary point.
    } else {
      x += u;    // Business as usual.
    }
  }

  // If we make it to here, it must be because either (1) we hit a
  // different digit, in which case we have prepared an x that is correct
  // except for the binary point, or (2) a and b agree on all
  // their leftmost min(len(a), len(b)) digits.  For (2), it must therefore be
  // that b has more digits (and thus more '1' digits), because if a
  // had more it would necessarily be larger than b, which is impossible.
  // In this case, x will simply be a.
  // So in both cases (1) and (2), all we need to do is fix the binary point.
  if (x.length > 1) x = '0.' + x.substr(1);
  return x;
};