base_minus_two.js

'use strict';

const m = -2;

function prepare(n) {
  let b = 1;
  let min = 0;
  let max = 1;

  const bs = [1];
  const mins = [0];
  const maxs = [1];

  for (let i = 1; i < n; i++) {
    b *= m;
    if (b > 0) max += b;
    if (b < 0) min += b;

    bs.push(b)
    mins.push(min)
    maxs.push(max)
  }

  return {bs, mins, maxs};
}

const {bs, mins, maxs} = prepare(20);

function find(t) {
  const n = bs.length;
  for (let i = 0; i < n; i++) {
    if (t >= mins[i] && t <= maxs[i]) {
      return i;
    }
  }
}

function findFormRight(t, from) {
  const n = bs.length;
  let min = n;
  for (let i = from; i >= 0; i--) {
    if (t >= mins[i] && t <= maxs[i] && i < min) {
      min = i
    }
  }

  return min;
}

function encode(target) {
  let bi = find(target);
  target -= bs[bi];
  const answer = [1];
  let lbi = bi;

  let c = 0;

  while (target !== 0) {
    let bi = findFormRight(target, lbi - 1)
    target -= bs[bi];

    for (let i = lbi - 1; i > bi; i--) {
      answer.push(0);
    }

    answer.push(1);

    lbi = bi;
  }

  return answer.reverse();
}

function decode(a) {
  const n = a.length;
  let ans = 0;
  for (let i = 0; i < n; i++) {
    if (a[i] === 1) ans += bs[i];
  }

  return ans;
}

console.log('---------------');
console.log(`-23 => [${encode(-23)}] => ${decode(encode(-23))}`);
console.log(`23 => [${encode(23)}] => ${decode(encode(23))}`);
console.log('---------------');
console.log(`9 => [${encode(9)}] => ${decode(encode(9))}`);
console.log(`-9 => [${encode(-9)}] => ${decode(encode(-9))}`);