仅使用一个指示位来平衡 1 和 0 范围的最佳算法？

Question

上下文：8b/10b、64b/66b 和 128b/130b 等线路编码有助于硬件使用外部状态平衡 0/1。我的问题只涉及软件，而不是硬件，并且不是外部状态来实现最终的 1s/0s 平衡，我正在寻找最佳算法来仅使用 1 个上下文/指示器位来一次性平衡 1 和 0 的输入而不是 2，充分认识鸽巢原理使得“完美平衡”在这里变得不可能。 （也就是说，我希望输出中的 1 和 0 的平衡比仅使用此单个上下文位的输入“通常更好”/“不差于”。） TL;DR：假设我有一个 16 位整数，其中最高位可以任意选择。我想将 32768x 输入分别映射到 65536 个可能输出中的一个，但具有更好的 1/0 平衡。演示：

(i.oninput = function() {
  var val=parseInt(i.value.replace(/[^01]/g,"").slice(-15),2)|0;
  var ind=Math.abs(bitCount(val&0xff)-4)>=Math.abs(bitCount(val>>8)-4)|0;
  var out=val ^ (0xff << 8*ind);
  var balIn=bitCount(val)-8, blOut=bitCount(out)-8;
  p.textContent="Input:  "+val.toString(2).padStart(16,0)+"\nIndic.: "+
    ind+"\nOutput: "+out.toString(2).padStart(16,0)+"\n\nBalance in:  "+
    (balIn<0?balIn:"+"+balIn)+"\nBalance out: "+(blOut<0?blOut:"+"+blOut)
})();
function bitCount(n) {
  n |= 0, n = n - ((n >>> 1) & 0x55555555) | 0;
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333) | 0;
  n = Math.imul((n + (n >> 4)) & 0xF0F0F0F, 0x1010101)|0;
  return (n >>> 24)|0;
   }

Enter 15x 1s/0s: <input type=text style=width:10em id=i value=100000000000011><br><br><pre id=p></pre>

平衡是 1s/0 计数彼此相等的距离：0100000000000011 有 3x 1 和 13x 0，完美的平衡是 8x 1s/0，因此两者都距离最佳值 5 个点。上述极其简单的算法计算 15 位整数的低半部分和高半部分中的位数，并决定与低 8 位或高 8 位进行异或 0xff。这是“极其简单”的，只是为了展示我想要实现的目标；我正在寻找一种性能更好的好算法，并且可以推广到适用于任何大小的 1 和 0 字符串。

在 65536 种可能的 16 位组合中，7 位设置有 11440 种组合，8 位设置有 12870 种组合，9 位设置有 11440 种组合。

将它们加在一起可以得到 35750 个组合，最多平衡一位，这足以编码 15 位——不错，事实上，这适用于所有偶数位长度最多 18 的情况。 因此，用 1 个额外位就能实现的最佳平衡实际上非常好。 不幸的是，我只知道计算特定输入的编码的缓慢/昂贵的方法，例如迭代可能的位数集，然后用该位数集计算第 n 个值。

Answer 1