Context: line encodings like 8b/10b, 64b/66b and 128b/130b help hardware balance the 0s/1s using an external state. My question only concerns software, not hardware, and instead of an external state to achieve eventual 1s/0s balance, I am search for the optimal algorithm to one-time balance an input of 1s and 0s using only 1 context/indicator bit instead of 2, acknowledging full well the pigeon-hole principle makes perfect balance impossible here. (That is, I want an often better / no worse than balance of 1s and 0s in the output than the input using only this single context bit.)

TL;DR: Let’s say I have a 16-bit integer where the highest bit can be arbitrarily chosen. I want to map the 32768x inputs each to a single one of the 65536 possible outputs but with better 1s/0s balance. Demo:

(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)+"nnBalance 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>

The balance is how far away the 1s/0s counts are from equaling eachother: 0100000000000011 has 3x 1s and 13x 0s and a perfect balance would be 8x 1s/0s, so both are 5 points away from optimal. The above extremely simplistic algorithm counts the number of bits in the low and high half of the 15 bit integer and decides to xor 0xff against either the lower 8 bits or the upper 8 bits thusly. This is extremely simplistic and meant only to demonstrate what I’m trying to achieve; I’m looking for a good algorithm that performs much better AND is generalized to work for any size string of 1s and 0s.

Since this is stack-overflow and I expect to be flamed for not already knowing the answer (which secondarily precludes perfect concise explanations of question as my goal here is to learn, not to flout my knowledge), I will answer some anticipated Q/A:

• Q: are you writing your software in JavaScript? A: No and there is no JavaScript tag as such. This is a question about algorithms and I included the above demo to try to clarify what I’m trying to achieve.
• Q: because you already have a working algorithm, why even post on here? A: No, I do not have a working algorithm and I couldn’t find any through extensive online research. The above algorithm helps balance many inputs but is far from optimal. I am eager to learn the best algorithm, not the half-ass demo algorithm I posted in the demo.
• Q: this is offtopic because it is unclear what you are asking. A: you say that about every question everyone posts and it’s ridiculous! Please, run the demo and see this is a very specific definable question: what algorithm provides the best 1/0 balancing using only one indicator bit, knowing full well no algorithm can be perfect in this constraint.
• Q: if its only 16 bits, why not brute force test all and make an optimized table? A: because I’ll actually be working with mapping 127 bit inputs to 128 bit outputs, so I’ll need a generalized solution I can test and verify on smaller-length integers. The 16-bit demo is purely for illustration.