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

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

---

编辑2另一种算法是迭代2^-n并检查其中是否有任何多个符合该区间.然而,这将更昂贵.

Answer 1

function bin(a, b) {
 var den = 1;
 while (true) {
  var bint = Math.floor(b);
  if (bint == b) bint--;
  if (a <= bint) {
   return bint / den;
  }
  den *= 2;
  a *= 2;
  b *= 2;
 }
}

该代码迭代越来越大的二次方分母 ( den)，直到找到支持适合该范围的值的分母。