基于单个指示位的0/1序列单次平衡最优算法求询

背景 #

8b/10b、64b/66b、128b/130b等线路编码依赖外部状态帮助硬件实现0/1平衡。本次问题聚焦软件场景，无需依赖外部状态实现最终0/1平衡，而是要设计一种最优算法：仅使用1个上下文/指示位（而非2个）对输入的0/1序列进行单次平衡。需明确：鸽巢原理决定完美平衡在此场景下不可能实现，算法目标是让输出的0/1平衡效果通常更优或不逊于输入。

核心需求 #

假设存在一个16位整数，其最高位可任意选择。需将32768种输入分别映射至65536种可能输出中的一种，且输出的0/1平衡效果更优。演示示例如下：

演示代码 #

JavaScript 实现

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

HTML 交互界面

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

平衡度定义 #

平衡度指0/1数量与完全相等状态的差距：例如序列0100000000000011有3个1、13个0，完全平衡状态为8个1和8个0，因此其与最优状态的差距为5。

优化目标 #

上述演示算法通过统计15位整数高低半部分的比特数，决定对低8位或高8位异或0xff，仅作功能演示使用。现需寻求性能更优且可适配任意长度0/1序列的算法。

内容的提问来源于stack exchange，提问作者Jack G