Optimal algorithm for balancing a span of 1s and 0s using only one indicator bit?

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)+"\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>

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.

The question boils down to for any given word length N how many of the possible 2^N states can be represented by N/2 1's and N/2 0's and how far away from perfection do we have to go to represent at least 2^(N-1) states. A perfect solution is only possible for N=2. These solutions represent the optimal encodings with the smallest deviation from the ideal of equal numbers of 1' and 0's.

Here is the code to find the optimal bit patterns - apologies for any MSVC quirks left in

#include <iostream>
#include <inttypes.h>

int countbits(int x)
{
   int i = 0;
   while (x)
   {
      while (!(x & 1)) x >>= 1;
      if (x) i++;
      x >>= 1;
   }
   return i;
}

uint64_t equalbits(int N)
{   
  // beware of integer overflow when N > 60 change to double to go higher
  // compute the entries closest to the centre of Pascal's triangle.
  uint64_t work = 1;
  int n = (N+1) / 2;
  work = 1;
  if (!(N & 1)) work = 2;
  for (int i = 2; i <= n; i++)
     work = work*2* (2*i - 1) / i;
  return work;
}

void deeptest(int N)
{
  // begins to creak when N > 60 verified against FP version up to there.
  // change "unsigned unint64_t" to "double" to go further but with 53 bit precision

  uint64_t centre = equalbits(N);
  uint64_t exact, next1, next2, result, twoNm1 = 1;
  if (N == 1) printf("\n\n        N   solution \t\t2^(N-1)\t\t   exact \t     1-bit\t\t2-bit\n");
  twoNm1 <<= N-1;
  next1 = (centre * (N / 2)) / (N / 2 + 1);
  if (N & 1)
  {
     next1 = centre; // odd N always 1 bit error
     exact = 0;
  }
  else
     exact = centre;
  result = exact + 2 * next1;
  if (result >= twoNm1) printf(" pass "); else printf(" fail ");
  printf(" %2i : %-18I64u  %-18I64u %-18I64u %-18I64u \n", N, result, twoNm1, exact, next1);
  if (result < twoNm1)
  {
     next2 = (centre * (N / 2 - 1)) / (N / 2 + 2);
     result += 2 * next2;
     if (result >= twoNm1) printf(" pass2"); else printf(" fail ");
     printf(" %2i : %-18I64u  %-18I64u %-18I64u %-18I64u %-18I64u \n", N, result, twoNm1, exact, next1, next2);
  }
}

void brute_force(int N)
{
  int bits[65536], lut[36000];
  int i, j, twoN, result, counts[17];
  twoN = 1 << N;
  printf("\n N = %i : 2^N = %-7i\n", N, twoN);
  for (i = 0; i < twoN; i++) bits[i] = countbits(i);

  for (j = 0; j <= N; j++)
  {
     int count = 0;
     for (i = 0; i < twoN; i++) if (bits[i] == j) count++;
     printf(" %i : %i\n", j, count);
     counts[j] = count;
  }
  if (N & 1)
     result = counts[N / 2] + counts[N / 2 + 1];
  else
     result = counts[N / 2] + 2 * counts[N / 2 + 1];
  if (result * 2 > twoN) printf("pass "); else printf("fail");
  printf(" states %i vs %i 2^(N-1)\n", result, twoN / 2);
  j = 0;
  for (int i = 0; i < twoN; i++) if (abs(bits[i] - N/2) < 2) lut[j++] = i; 
}

int main()
{
  printf("Number of states for word length N with exact, 1-bit and 2-bit errors\n\n");
  for (int i = 1; i <= 16; i++) brute_force(i);
  for (int i = 1; i <= 60; i++) deeptest(i);
}

This corresponds to the centre line peak of Pascal's triangle for N = 2N and the equal pair nearest the centre for N = 2N+1. Then working outwards allowing increased bit count. This program generates the solutions for N = 1 to 16 by brute force and builds the encoding lookup table. It explores N = 1 to 60 using 64 bit integers. It can be trivially altered to use double precision instead of uint64_t reals to reach N=170.

This is a quick summary table of the output for the first 18 values of N which is the limit where a representation by no more than 1 bit out of balance still works.

 solution = exact + 2*(1-bit + 2-bit + ...)

Result for N=2 is exact.

All the others must have at least some states used with a 1-bit error. So long as you can afford to have lookup tables then encoding and decoding is O(1). Generating the tables by brute force is clearly O(2^N).

170| 4 |

There might possibly be a way to encode/decode with complexity O(N*logN) but that is another question entirely. For N>60 only solutions for even N were tested. The problem gets a lot stiffer for N>60.