Compact Binary Representation

Question

Background

Often, when storing a number in binary with some maximum, we simply round the maximum to the next power of two then allocate the number of bits nececairy to store the whole range. Lets call the result of this method \$S(x, m)\$ where x is the number and m is the maximum.

While not bad, the naive has a few bits of redundancy since some bit patterns could only lead to a number beyond the max. You can exploit this to create a slightly shorter variable-length representation for numbers.

The format

I will define such a format as follows:

• Let x be the number we want to represent and m be the max
• Let d the the difference between m and the next smaller power of 2. (in other words with the first 1 chopped of the binary representation)
• If m is 0, return the empty string
• If x is less than or equal to d:
  • Output "0" followed by f(x, m)
• Otherwise:
  • Output "1" followed by the log2(m)-bit binary representation of x-d-1.

Python translation:

def d(x): return x-(1<<x.bit_length()-1)

def f(x, m):
    if m==0:
        return ''
    if m==1: # edge cases needed to deal with the fact that binary coding in python produces at least one 0 even if you specify 0 digits
        return f'{x}'
    if x<=d(m):
        return '0'+f(x,d(m))
    else:
        return f'1{x-d(m)-1:0>{m.bit_length()-1}b}')

Challenge

Output a pair of functions f(x,m) and f'(y,m) that convert to and from compressed binary representation for a given maximum.

You may assume m>3 and x<=m.

The binary representation can be as a string, integer, list of ints, decimal coded binary, or anything else reasonable.

If you prefer you can take m+1 as input instead of m. (exclusive maximum)

Test Cases

Rows are X, columns are M

     5      6      7      8      9      10     11     12     13     14     15     16     17     18     19     20     21     22     23    
     ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------
    0 00     00     000    0      00     00     000    00     000    000    0000   0      00     00     000    00     000    000    0000  
    1 01     010    001    1000   01     010    001    0100   001    0010   0001   10000  01     010    001    0100   001    0010   0001  
    2 100    011    010    1001   1000   011    010    0101   0100   0011   0010   10001  10000  011    010    0101   0100   0011   0010  
    3 101    100    011    1010   1001   1000   011    0110   0101   0100   0011   10010  10001  10000  011    0110   0101   0100   0011  
    4 110    101    100    1011   1010   1001   1000   0111   0110   0101   0100   10011  10010  10001  10000  0111   0110   0101   0100  
    5 111    110    101    1100   1011   1010   1001   1000   0111   0110   0101   10100  10011  10010  10001  10000  0111   0110   0101  
    6        111    110    1101   1100   1011   1010   1001   1000   0111   0110   10101  10100  10011  10010  10001  10000  0111   0110  
    7               111    1110   1101   1100   1011   1010   1001   1000   0111   10110  10101  10100  10011  10010  10001  10000  0111  
    8                      1111   1110   1101   1100   1011   1010   1001   1000   10111  10110  10101  10100  10011  10010  10001  10000 
    9                             1111   1110   1101   1100   1011   1010   1001   11000  10111  10110  10101  10100  10011  10010  10001 
   10                                    1111   1110   1101   1100   1011   1010   11001  11000  10111  10110  10101  10100  10011  10010 
   11                                           1111   1110   1101   1100   1011   11010  11001  11000  10111  10110  10101  10100  10011 
   12                                                  1111   1110   1101   1100   11011  11010  11001  11000  10111  10110  10101  10100 
   13                                                         1111   1110   1101   11100  11011  11010  11001  11000  10111  10110  10101 
   14                                                                1111   1110   11101  11100  11011  11010  11001  11000  10111  10110 
   15                                                                       1111   11110  11101  11100  11011  11010  11001  11000  10111 
   16                                                                              11111  11110  11101  11100  11011  11010  11001  11000 
   17                                                                                     11111  11110  11101  11100  11011  11010  11001 
   18                                                                                            11111  11110  11101  11100  11011  11010 
   19                                                                                                   11111  11110  11101  11100  11011 
   20                                                                                                          11111  11110  11101  11100 
   21                                                                                                                 11111  11110  11101 
   22                                                                                                                        11111  11110 
   23                                                                                                                               11111

Answer 1

JavaScript (ES6), 65 + 67 = 132 bytes

Encoder (65 bytes)

Expects (x)(m) and returns a binary string.

x=>g=m=>m?x>(m-=q=1<<Math.log2(m))?(q|x+~m).toString(2):0+g(m):""

Try it online!

Commented

x =>                  // outer function taking x
g = m =>              // inner recursive function taking m
m ?                   // if m is not zero:
  x > (               //   if x is greater than
    m -=              //   the updated value of m defined as
    q =               //   m - q, where q is the highest
    1 << Math.log2(m) //   power of 2 less than or equal to m,
  ) ?                 //   then:
    (q |              //     use q for the leading 1
         x + ~m)      //     use x - m - 1 for the payload data
    .toString(2)      //     convert to binary
  :                   //   else:
    0 +               //     append a 0 and
    g(m)              //     do a recursive call with the updated m
:                     // else:
  ""                  //   stop

Decoder (67 bytes)

Expects (x,m), where x is a binary string. Returns an integer.

f=([c,...x],m)=>c?[f(x,m-=1<<Math.log2(m)),m-~`0b${x.join``}`][c]:0

Try it online!

Commented

f = (                    // f is a recursive function taking:
  [c,                    //   c = next character in the binary string
      ...x],             //   x[] = array of remaining characters
  m                      //   m = maximum
) =>                     //
c ?                      // if c is defined:
  [                      //   return either:
    f(                   //     the result of this recursive call (*):
      x,                 //       pass x unchanged
      m -=               //       subtract from m the highest
      1 << Math.log2(m)  //       power of 2 less than or equal to m
    ),                   //     end of recursive call
    m - ~`0b${x.join``}` //     or m + x[] parsed as binary + 1
  ][c]                   //   according to c
:                        // else:
  0                      //   stop

_{* Because this call is enclosed in an array, it is always executed regardless of whether the result is actually used or ignored. Since each recursion is guaranteed to stop as soon as the input string is fully consumed, this has no harmful side effects other than performance degradation.}

Answer 2

Charcoal, 40 + 35 = 75 bytes

Encoder, 40 bytes

ＮθＮηＷθ«≔↨²Ｅ↨θ²∧λκζ¿›ηζ«1≧⁻⊕ζη≧⁻⊕ζθ»«0≔ζθ

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input m and x.

Ｗθ«

Repeat until m=0.

≔↨²Ｅ↨θ²∧λκζ

Calculate d by setting the most significant bit of m to zero.

¿›ηζ«

If x is greater than d, then...

1≧⁻⊕ζη≧⁻⊕ζθ

... output a 1 and subtract d+1 from x and m. This causes the rest of the bits to be encoded as binary.

»«0≔ζθ

Otherwise output a 0 and set m equal to d.

Decoder, 36 35 bytes

≔⍘Ｎ²θＩ∧Ση⊕⁺⍘⁺0Φθ›Σ…θκ⌕η1²⍘⁺0ΦηΣ…ηκ²

Try it online! Link is to verbose version of code. Explanation: Converts m to binary. If the value to be decoded contains any 1 bits, then a number of leading 1 bits is removed from the binary representation of m, and the first 1 bit is removed from the value to be decoded, and the two are then converted from binary, summed and incremented. Otherwise the output is simply zero.

Previous 36-byte decoder used a method similar to that of the encoder:

ＮθＦＳ«≔↨²Ｅ↨θ²∧λκζ¿Ｉι«Ｍ⊕ζ→≧⁻⊕ζθ»≔ζθ»Ｉⅈ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input m.

ＦＳ«

Loop over the bits to be decoded.

≔↨²Ｅ↨θ²∧λκζ

Calculate d by setting the most significant bit of m to zero.

¿Ｉι«

If the next bit is a 1, then...

Ｍ⊕ζ→≧⁻⊕ζθ

... add d+1 to x and subtract it from m. This causes the rest of the bits to be decoded as binary.

»≔ζθ

Otherwise set m equal to d.

»Ｉⅈ

Output the final value of x.