Compact coding of integer into bitstring I want to compactly code positive integers x into bits, in a manner allowing decoding back into the original integers for a stateless decoder knowing the maximum value m of each x; it shall be possible to uniquely decode the concatenation of encodings, as is the case in Huffman coding.
[The above introduction motivates the rest, but is not part of the formal definition]

Notation: for any non-negative integer i, let n(i) be the number of bits necessary to represent i in binary; that is the smallest non-negative integer k such that i&gt;&gt;k == 0

  i :   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  ..
n(i):   0   1   2   2   3   3   3   3   4   4   4   4   4   4   4   4   5   5   5   ..


I want a function F(x,m) defined for 0&lt;x and x&lt;=m, with output a string of '0' or '1', having these properties:


F(x,m) has length less than 2*n(x) or 2*n(m)-1, whichever is smaller.
If x&lt;y then:

F(x,m) is no longer than F(y,m);
F(x,m) and F(y,m) differ at some position over the length of F(x,m);
there's a 0 in F(x,m) at the first such position.

When for a certain m properties 1 and 2 do not uniquely define F(x,m) for all positive x at most m, we reject any encoding giving a longer F(x,m) than some otherwise acceptable encoding, for the smallest x for which the length do not match.


Note: In the above, implicitly, 0&lt;x, 0&lt;y, 0&lt;m, x&lt;=m, and y&lt;=m, so that F(x,m) and F(y,m) are defined.

It is asked the shortest program that, given any x and m meeting the above constraints and up to 9 decimal digits, outputs an F(x,m) consistent with the above rules. The following C framework (or its equivalent in other languages) is not counted:

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#define C(c) putchar((c)?'1':'0') // output '0' or '1'
#define S(s) fputs((s),stdout)    // output a string
typedef unsigned long t;          // at least 32 bits
void F(t x,t m);                  // prototype for F
int main(int argc,char *argv[]){
 if(argc==3)F((t)atol(argv[1]),(t)atol(argv[2]));
 return 0;}
void F(t x,t m) {   // counting starts on next line
}                   // counting ends before this line




Comment: Property 1 aggressively bounds the encoded length; property 2 formalizes that unambiguous decoding is possible, and canonicalizes the encoding; I assert (without proof) this is enough to uniquely define the output of F when m+1 is a power of two, and that property 3 is enough to uniquely define F for other m.

Here is a partial table (handmade; the first version posted was riddled with errors, sorry):

  x     :   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
F(x,1)  : empty
F(x,2)  :   0       1
F(x,3)  :   0       10      11
F(x,4)  :   0       10      110     111
F(x,5)  :   0       10      110     1110    1111
F(x,6)  :   0       100     101     110     1110    1111
F(x,7)  :   0       100     101     1100    1101    1110    1111
F(x,8)  :   0       100     101     110     11100   11101   11110   11111

F(x,15) :   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111
Python, 171
def F(x,m):
 a=0;b=[9]
 while len(b)&lt;m:
    if 4**len(bin(len(b)))*2&gt;64*a&lt;4**len(bin(m)):
     if(a&amp;a+1)**a:b+=[a];a+=1
     else:a*=2
    else:a=b.pop()*2
 return bin((b+[a])[x])[2:]

Note that lines that appear to begin with 4 spaces actually begin with a tab.
Testing, with bitpwner's test script:
         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15      
F(x,1)   0       
F(x,2)   0        1       
F(x,3)   0        10       11      
F(x,4)   0        10       110      111     
F(x,5)   0        10       110      1110     1111    
F(x,6)   0        100      101      110      1110     1111    
F(x,7)   0        100      101      1100     1101     1110     1111    
F(x,8)   0        100      101      110      11100    11101    11110    11111   
F(x,9)   0        100      101      110      11100    11101    11110    111110   111111  
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111  
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111  
F(x,12)  0        100      101      1100     11010    11011    11100    11101    111100   111101   111110   111111  
F(x,13)  0        100      101      1100     11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111  

Explanation:
This is all based on the observation that between two consecutive elements of the code, F(x,m) and F(x+1,m), we always add one to the binary number, then multiply by two some number of times. If these steps are followed, then it is a valid code. The rest simply tests to make sure it is short enough.
Golfs:
175 -&gt; 171: changed 2**(2*... to 4**