javascript - 在给定的时间间隔内找到最短的二进制字符串

Question

假设我有两个值 0 <= a < b <= 1 , 我怎样才能选择 x这样 a <= x <强> < b用最短的二进制扩展可能吗？

到目前为止，我的方法是采用 a 的二进制字符串和 b , 去掉小数点，首先它们不同，展开 a直到那时。如果有更多 a消费，剥去最后一点。最后，添加 1 .

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

这行得通，但我不相信它通常是正确的。有什么想法吗？...

---

编辑 我已经找到了一个无法正常工作的案例 :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 另一种算法是遍历 2^-n并检查它的任何倍数是否在区间内。但是，这会更昂贵。

Answer 1

对于像 a = 0.1、b = 0.100001(二进制——即 a = 0.5、b = 0.515625，十进制)这样的输入，它将失败。在这种情况下，正确答案是 0.1，但您的算法将生成 0.11，这不仅不是最小长度，而且大于 b :-(

你的数字检查对我来说看起来很好——问题是当你做出(正确的)决定结束循环时，如果 b 的数字字符串更长，你会构造错误的输出。一种简单的修复方法是在进行过程中一次输出一个数字:直到您看到不同的字符，您知道您必须包括当前字符。

另一个提示:我不太了解 Javascript，但我认为这两个 parseInt() 调用都是不必要的，因为您对 u 或 没有任何作用v 实际上需要算术。

[编辑]

下面是一些示例代码，其中包含一些其他注意事项:

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