[Question]
  [
## Background
[**Elias omega coding**](https://en.wikipedia.org/wiki/Elias_omega_coding) is a universal code which can encode positive integers of any size into a stream of bits.
Given a positive integer \$N\$, the encoding algorithm is as follows:
1. Start with a single zero in the output.
2. If \$N=1\$, stop.
3. Prepend the binary digits of \$N\$ to the current output.
4. Let \$N\$ be the number of digits just prepended, minus one. Go back to step 2.
In Python-like pseudocode:
```
n = input()
s = "0"
while n > 1:
    # bin(n) is assumed to give a plain string of bits, without "0b" prefix
    s = bin(n) + s
    n = len(bin(n)) - 1
output(s)
```
## Illustration
The number 1 gets encoded into a single `0`.
The number 21 gets encoded into `10100101010`, or `10 100 10101 0` in chunks, where each chunk is added to the output stream in the following order: first "0" by default, then the binary of 21, then 4 (the bit length of 21 minus 1), then 2, then stop.
## Task
Given a positive integer \$N\$, output its Elias omega code.
You can take the input number \$N\$ in any convenient format, including its representation in binary.
The output must be a valid representation of a flat stream of bits, which includes:
* a plain string or array of zeros and ones, or
* a single integer whose binary representation corresponds to the stream of bits.
Outputting the bits in reverse or outputting a nested structure of bits (e.g. `["10", "100", "10101", "0"]` for 21) is not allowed.
Shortest code in bytes wins.
## Test cases
```
N     => Omega(N)
1        0
2        100
3        110
4        101000
5        101010
6        101100
7        101110
8        1110000
12       1111000
16       10100100000
21       10100101010
100      1011011001000
345      1110001010110010
1000     11100111111010000
6789     11110011010100001010
10000    111101100111000100000
1000000  1010010011111101000010010000000
```
This is OEIS [A281193](http://oeis.org/A281193).
  
[Answer]
# [Dodos](https://github.com/DennisMitchell/dodos), ~~96~~ ~~91~~ 90 bytes
```
	> > E
	+ >
E
	E - + L B
	> B
B
	B + L H
	+ H
L
	>
	> -
H
	H - -
	+ >
-
	dip
+
	dot
>
	dab
```
[Try it online!](https://tio.run/##JYsxDoAgFENneoruhEEPwEBCwsAlNH9hwkTv/y06vbR9tWnzdg@ZmRUhMkOoTIzsLNBQIJQvt2U0dNVrSVDR5Kb/Kdi4EIX5QIodp7vv2ws "Dodos – Try It Online")
I've re-discovered this crazy and wonderful language today, so I've wasted two hours building this :D
### Explanation
Dodos programs are composed by a series of function definitions, each non-indented symbol here is a function name and the indented lines following the symbol are the definition (the first 2 lines are the definition of the main function).
Each function takes a list of number as input and produces new list by concatenating in a list the outputs of the definitions of each line. Each line can be interpreted as function composition, where `F G H` means `F(G(H(input)))`.
Recursion is where the crazy part really start: if while computing a function `F(x)` we try computing `F(y)` for any `y≤x`, then Dodos surrenders and returns the input unchanged. This prevents infinite recursion from happening, and it is the only form of conditional branching in the language. It can take a while to enter the right mindset to write anything in Dodos ^^"
So, starting from the bottom let's see what these functions are doing:
`dab`, `dot`, and `dip` are the only three builtin commands in Dodos, here redefined as `>`, `+`, and `-` to save bytes in the rest of the program. `dab` returns the input list without the first element; `dot` sums all elements of the input list (and returns 0 if the list is empty); `dip` subtracts 1 from each element of the list **and then takes the absolute value of each element**: negative numbers don't exist in Dodos! Any time we try to subtract 1 from 0 we obtain 1 as a result.
I had originally written much more about the rest, but this post is long enough as it is, so I will only provide descriptions of the input/output of each function. Trying to understand how each function works can be a good exercise, but if you want more information leave me a comment and we can discuss more in chat :)
`H` - Input: a number `n`. Output: `n%2` followed by (0 repeated `n//2` times)
`L` - Input: a list of 0s and 1s `l`. Output: `[tail(l),tail(l) with each bit flipped]` (hint: `+ L` will compute the length of `l` - 1)
`B` - Input: a number `n`. Output: the binary representation of `n`, with a leading `0`
`E` - Input: a number `n`. Output: the Elias omega coding of `n`, with an extra leading `01` and missing the trailing `0`.
`main` - Input: a number `n`. Output: the Elias omega coding of `n`.
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~16 13~~ 11 bytes
```
ṁḋ↔Θ↑←¡ȯ←Lḋ
```
[Try it online!](https://tio.run/##yygtzv7//@HOxoc7uh@1TTk341HbxEdtEw4tPLEeSPkARf///29kCAA "Husk – Try It Online")
Outputs a flat boolean array.
-2 using the idea from Jonathan Allan's answer.
## Explanation
```
ṁḋ↔Θ↑←¡ȯ←Lḋ
      ¡ȯ    create an infinite list using:
         Lḋ length of binary digits
        ←   decremented  
    ↑       take the longest prefix with:
     ←       elements that aren't falsy when decremented(1)
   Θ        prepend 0 to that
  ↔         reverse
ṁḋ          convert each to binary and flatten
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~11~~ 10 [bytes](https://github.com/DennisMitchell/jelly)
Is there a trick to make for shorter code?
```
BL’ƊƬṣ1UBF
```
A monadic Link accepting a positive integer which yields a list of ones and zeros.
**[Try it online!](https://tio.run/##y0rNyan8/9/J51HDzGNdx9Y83LnYMNTJ7f///2bmFpYA "Jelly – Try It Online")**
### How?
```
BL’ƊƬṣ1UBF - Link: n           e.g. n=12
    Ƭ      - collect up starting with n until no change:
   Ɗ       -   last three links as a monad:        (3)     (1)     (0)
B          -     to binary            [1,1,0,0]    [1,1]   [1]     [0]
 L         -     length               4            2       1       1
  ’        -     decrement            3            1       0       0   <- 0=0: stop
             }                     -> [12,3,1,0]
     ṣ1    - split at ones            [[12,3],[0]]
       U   - upend                    [[3,12],[0]]
      B    - to binary                [[[1,1],[1,1,0,0]],[0]]
         F - flatten                  [1,1,1,1,0,0,0]
```
[Answer]
# JavaScript (ES6), 50 bytes
### With `.toString(2)`
```
f=(n,s=0,b=n.toString(2))=>n-1?f(b.length-1,b+s):s
```
[Try it online!](https://tio.run/##dZBdDoIwEITfPQWPbeRnFxHQBD2EJwAExJDWUOL1EQsxdIt97Hydzswzf@eq7NvX4Al5r8axzphwVQZukQl/kLehb0XDQs6zi/DwWrPC7yrRDA8P3WKv@FmNpRRKdpXfyYbVDB19OHeCwIGdKYZrEYHKB0NGKkfm6@k9JY6UsDxiQtghEkpYHqkZ85uDIhiayEZWjGkbbWRNhja20Wu6J71wcaQbR0caXhtq2jYFk0V9YKtynKQnUhnnqMsXG@Zg8MsH8GeJ@RLMwdaBfhMCjB8 "JavaScript (Node.js) – Try It Online")
### Without `.toString(2)`
```
f=(n,i,q=n*2>>i)=>n>!!i?q?f(n,-~i)+q%2:f(i-2,1):''
```
[Try it online!](https://tio.run/##dZDNDoIwEITvPgUeDFRBdit/koDPYtSaGlJEjEdfHbEQQ7fYY@frdGZux9exPT3k/Rmo@nzpOlF4ypd@U6g1L0vJilKVy6U8NAfRC8Fbsk2z4rnwZMB9ZLnrdqdatXV12Vb11RMeOvow5oShAwtT5FMRgco7Q0YqR@br/j0lYkpYHgkh7BApJSyPzIz5zUER5CYykxUT2kYbWZOhjc306u9JLxwd6cZRTMNrQ03bpmCyqA/MVU7SbE8q4xB1/GLGHAx@/AD@LDFcgjnYNNBvQoDuAw "JavaScript (Node.js) – Try It Online")
[Answer]
# [J](http://jsoftware.com/), 29 28 bytes
```
1;@}.1#:&.>@|.&|.<:@#@#:^:a:
```
[Try it online!](https://tio.run/##pdNNCsIwEAXgvacYLBgFG2Zq1Rp/CAiuXHkAQcQgbryAnj1Go9a2SalNS2lWXx8zrxfd5UzBUgCDISAI88Qc1rvtRtNc3jlFosdX8sZ7N74QMpKR2IuD0IPO6Xi@ggJK7Ikx@@4PcQAQCwi6jPs5WpZMMAxzFSRlk8LNUTWnzdpaVpC6TQoxxy6TwnJO3GZQzml1R595tlQVZC6TwkxKPHvP0/5pG3NSY7ZqgOk8efZOpbyNXZMT0bejPGmuN5DNf5SO3Sb93PhPF1450bN3Ksy0mL1GNp2fZjOnWcyLzbtgc6K/S74JVPv2/c7bfKr6AQ "J – Try It Online")
This approach, which I prefer to the strightforward recursion, is thanks to [Jonathan Allen's nice idea](https://codegolf.stackexchange.com/a/219114/15469).
-1 thanks to Bubbler
* `<:@#@#:^:a:` Iteratively convert to binary `#:`, get size `#`, and decrement `<:`, keeping track of results `a:`.
* `1...&|.` Reverse both arguments `&|.` (1 on the left, and the output of the previous step on the right). A golfy way to include the constant 1 (which is unaffected by reversal, and which we'll use in the next step) while reversing step 1's output.
* `|.` Rotate by 1. So now we have the output of step 1 reversed and rotated left by 1. Importantly, the `0` is now in the correct place all the way on the right, though we still have a stray `1` at the beginning...
* `#:&.>@` Convert to binary `#:` under open `&.>`. A golfy way to convert every element to binary and box it.
* `1;@}.` Kill the first element `1...}.` (the stray `1`) and raze `;` (unbox so we have a single list of numbers)
## [J](http://jsoftware.com/), 29 bytes (recursive approach)
```
0&g=.((,~g<:@#@])#:)`[@.(1=])
```
[Try it online!](https://tio.run/##pdPBCoJAEAbge08xJLQKusxYqS0JQtCpU9cIgmiNLr1Br25bm5m5G@Yq4p4@f2Z@L9WYMwm5AAYhIAj1RBxW2826wkmZc98Pb@VSFF6xDzwRHHYF9ynfB1UwOh3PV5BAsT4xpt8IEAlwuhRaH7VJSnV0JcTfJrmb025OnXWwLGFmNsnFnJtMcsuZmE2nnGl3R/U8B6oSMpNJbibFlr03af@0lZn8MAc1QHWeLHunr7y9XZUT0bajJmmj95DVfzSbm036uPGfLjxzomXv1JppO/sPWXU@zRZGs50X@3dB50R7l2wT6Pbt/Z2X@VCrOw "J – Try It Online")
-3 thanks to Bubbler's realization we could 1-line it
Straightforward implementation of the recursion formula.
[Answer]
# [Add++](https://github.com/cairdcoinheringaahing/AddPlusPlus), 70 bytes
```
D,f,@,BBBFJ
D,g,@,bL1_
+?
n:x
y:'0'
Wn,`s,$f>x,`x,$g>s,`y,s+,`n,x-1
Oy
```
[Try it online!](https://tio.run/##S0xJKSj4/99FJ03HQcfJycnNi8tFJx3ITvIxjOfStufKs6rgqrRSN1DnCs/TSSjWUUmzq9BJqNBRSbcr1kmo1CnW1knI06nQNeTyr/z//78FAA "Add++ – Try It Online")
Add++ isn't too golfy.
`f` is a function that converts its input to a binary string. `g` gets a string and returns it's length minus one.
We then set **x** and **n** equal to the input, and **y** equal to the string `'0'`. Now, we enter a while loop, looping while **n** is non-zero. The loop has the following steps:
* Set **s** equal to `f(**x**)`
* Set **x** equal to `g(**s**)`
* Prepend **s** to **y**
* Set **n** equal to **x - 1**
Finally, output **y**
[Answer]
# [Vyxal](https://github.com/Lyxal/Vyxal), `d`, ~~15~~ ~~13~~ ~~11~~ ~~10~~ 9 bytes
```
≬bL‹↔1€Rb
```
[Try it Online!](http://lyxal.pythonanywhere.com?flags=d&code=%E2%89%ACbL%E2%80%B9%E2%86%941%E2%82%ACRb&inputs=12&header=&footer=)
## Explained (old)
```
≬bL‹↔1€Rb
≬bL‹         # lambda: len(bin(argument)) - 1
   ↔        # generate_until_no_change(^, input)
     1€      # ^.split(1)
       R     # map(reverse, ^)
        b    # bin(^)
             # `d` flag: deep_sum(^)
```
[Answer]
# [Perl 5](https://www.perl.org/) `-n`, 58 bytes
```
while($_>1){unshift@a,$_=sprintf"%b",$_;$_=y///c-1}say@a,0
```
[Try it online!](https://tio.run/##K0gtyjH9/788IzMnVUMl3s5Qs7o0rzgjM63EIVFHJd62uKAoM68kTUk1SQnItQaKVOrr6yfrGtYWJ1YClRj8/29k@C@/oCQzP6/4v66vqZ6BocF/3TwA "Perl 5 – Try It Online")
[Answer]
# [Rust](https://www.rust-lang.org/), ~~129~~ 87 bytes
```
|mut n|{let mut s=0.to_string();while n>1{let b=format!("{:b}",n);n=b.len()-1;s=b+&s}s}
```
[Try it online!](https://tio.run/##jZFBj4IwEIXv@ytGDqbNuqbjIuqS@lcMJHUlgZqlNR6Q345QKsXLtpxK8r33Zt7UN6W7s4QqKySh0EApNAjg3aO6aZCPZvgfnoqztb6elK4L@Utoer8UpQB5REPk/Hytq0wvSNT85G20kjSVPF@Xonf9wlTx/HOpWtV26QdkSolan8TfgjhVrwFBkNIVRCyi/2MbgyHzgt8jiF4wto69p5fdTqzfN3mxAcPuJtbvu7eLDfN6Ydy86JD1MHFdGHv/OXCuCKmlB10xaIO8x4y3s61NkFEGhDEnRPOxoOKS3f4wqw7H5Wx4SCxzapvNQksdKfZ2i/ns03VGq7Z7Ag "Rust – Try It Online")
My first Rust answer! ~~(and first time appeasing the Rust compiler gods)~~
A straight translation of the algorithm in the main post.
Ungolfed:
```
fn e(mut n: usize) -> String {
    let mut s = "".to_string();
    while n > 1 {
        let mut b = format!("{:b}", n);
        n = b.len() - 1;
        b.push_str(&s);
        s = b;
    }
    s+"0"
}
```
* -42 bytes from @Bubbler through a closure and miscellaneous golfs
[Answer]
# [K (ngn/k)](https://bitbucket.org/ngn/k), ~~25~~ ~~20~~ 18 bytes
-2 bytes thanks to coltim
```
1_,/|0,2\'(#1_2\)\
```
[Try it online!](https://tio.run/##JcbLCYAwEEXRVh64SAIRZyZfrSWQXVwIqcDeR9TNPfda5zlVx8Hdbzd5acYu3KW5psNYhiAgIiGjoIIFnCEMJkKI6ZWQS92/o79EDvoA "K (ngn/k) – Try It Online")
[Answer]
# [Ruby](https://www.ruby-lang.org/), 39 bytes
```
f=->n,s=?0{n>1?f[/.$/=~x="%b"%n,x+s]:s}
```
[Try it online!](https://tio.run/##VU/LDoIwELz7FRuj4WCFLvJQk8KHNMSogXiqhmKCQfx1hLIF7WlmZ3Z2Wj4vr64rxDZRTIuUNyrBtJCeu/LEpxbL9WW5Vqze6Oyo206CRAY8YwsA6TNATnjXYyQcDPNeIRqO1KqRodNiPFKr7oecYZc4@mYwp2FE6cZkm@A0nA/1lE4h2alqENojxm7EaYWThubxnypRvD/YMjgeooh5mZOBEvh/zRHz@QO/R6Yv9e5F5ubn6w0aeCsG@Rsez0pDCQIKqTI2IAG5W91PmoHjQNt9AQ "Ruby – Try It Online")
Recursive function that takes \$N\$ as an integer. A regex match returns the index of the last bit in the binary representation of \$N\$, which is equivalent to one less than the bit length of \$N\$.
[Answer]
# [Zsh](https://www.zsh.org/), 50 bytes
```
<<<${${1#?}:+`$0 ${$(([#2]$#1-1))#??} ''`}$1${2-0}
```
[Try it online!](https://tio.run/##qyrO@J@moanx38bGRqVapdpQ2b7WSjtBxUAByNPQiFY2ilVRNtQ11NRUtrevVVBXT6hVMVSpNtI1qP2vycWVpmAIwgYgAsICMw3AbKgwVBzEgZsJ4gMBxNT/AA "Zsh – Try It Online")
Neat recursive solution
```
<<<${${1#?}:+`$0 ${$(([#2]$#1-1))#??} ''`}$1${2-0}
                                          $1         # N
                                            ${2-0}   # $2, unless it is unset; then substitute "0"
   ${${1#?}:+                            }           # If after removing ?any digit from $1 there is something left, then substitute
             `$0                        `            # Backtick subshell, $0 is the current program
                 ${$(([#2]$#1-1))#??}                # Take the #length of $1, subtract one, substitute as 2#binary, remove the "2#"
                                      ''             # Add empty second argument to cause ${2-0} to substitute nothing on recursion
<<<                                                  # Print to stdout
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~57~~ 56 bytes
Saved a byte thanks to [ovs](https://codegolf.stackexchange.com/users/64121/ovs)!!!
```
f=lambda n:n>1and f(len(f'{n:b}')-1)[:-1]+f'{n:b}0'or'0'
```
[Try it online!](https://tio.run/##bVHBboMwDL3zFRaXEC1IMdDSRaU/0vVAIaioXUCQSdsqvp2FEFg7zRc/vzw/R3b7pS@Nisexym75@7nMQQl1wFyVUAU3qYKK3JU4D4SGSI8ixNOLYzhpOsLJqGWve8ggQAYRg5hBwmDDYMsgZbBjgIZFU0VGgJwbSbKxyMBtunudMXeJc@rJz1YWWpaTq899Br55sgldNUkXtHK4cosOraWDjz18nvVQPvmgU/yaWIFlVw5t8D8jcLZyLSvvGvg/k5@M1q8ZCfWKiyyuspv2QN4@ojQpCAOLMCbUq5oONJNQK/iu28BegsGyPSo8MDHdpgo0tUXb1UpPN9Vinw4QHuDei32MA9zdrKPMsv5k7j3@AA "Python 3 – Try It Online")
Inputs an integer and returns a string.
[Answer]
# Scala, 74 bytes
```
x=>{var n->r=x->"0";while(n>1){val b=n.toBinaryString;r=b+r;n=b.size-1};r}
```
[Try it online!](https://scastie.scala-lang.org/x6baD4erTouPj04TjyqdsQ)
So this is a bit embarrassing: the imperative version is 13 bytes shorter.
# Scala, 87 bytes
```
Seq.unfold(_){n=>val b=n.toBinaryString;Option.when(n>1)(b,b.size-1)}./:("0")(_.++:(_))
```
[Try it online!](https://scastie.scala-lang.org/uB4DEWGBQdG4wKQJuWtj7w)
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 19 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
@=¤T=U+T U=ÊÉ}f
Tj0
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QD2kVD1VK1QgVT3KyX1mClRqMA&input=Njc4OQ)
```
@ ... }f - return first falsey value returned by @
=¤       - convert input(U) to binary
T=U+T    - append to variable T(initially 0)
U=ÊÉ     - returns lenght -1 and assigns to U
Tj0      - discards first bit of T and implicitly print
```
[Answer]
# [C (clang)](http://clang.llvm.org/), ~~87~~ 86 bytes
```
l,a;g(n,b)char*b;{l=1;for(*b=48;n>1;n=a)for(a=0;bcopy(b,b+1,++l),*b=48+n%2,n/=2;)a++;}
```
[Try it online!](https://tio.run/##VVFRjoIwEP3vKSYmJq2MsUVENl08gnsA1w9AYEmwGNBNdg1nZ9uCwPaj7cx7M@9Nm6yTMlJ515UYyZwqjFnyFdWrWD7LUMisqukqDr1AqoOQKoyYyUQhl3FS3X5ojLEj0HFKhpbmqKWLahO6kkWOI9vuuyoucE@bO4VC3UEBexIwChA/siytTyA4hzOE8AQOrSSQU83CAQamM7dal2Z0sbzA@gDL5lMtENSLohktIbb549qcbCuBLm7Rwx36uMcAhYvCR1egFsOttzMnR38fvNkb73fOtT65RoUCamzqUaG3XeimHKQ@36EpftMqo0aMbYZAc5iGHacARmCY19rRJWczRNsdwazwAB/XNI/okREBw@LEfV21EbIdA8GJNyHGJNnNY437s9gU7@exxoOpmR2SCHdK2I7Cnyv0L0Fc8T9ptcxXTVpiYBP9oHMJS7aYKeATIuzqFYh5/JkN0UsM5baQj@hQzEd3w3dNluetxyE4/wM "C (clang) – Try It Online")
* saved 1 thanks to @ceilingcat suggestion of using Linux bcopy instead of memcpy.
* function tacking a number `n` and a buffer `b`.
# Explanation
* `l` length of result, used to shift the buffer.
* `a` length of current `n`.
* second for loop shifts the buffer by one and push next bit at the beginning.
* first loop resets `n` to length `a` which is already minus 1.
* initially we set `l` to 1 and the first bit to '0'
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 14 bytes
```
É?T=¢+T,ß¢ÊÉ:T 
É?             // If input U - 1, aka if U > 1,
   =           // then assign
    ¢          // U to a binary string
     +T        // plus builtin variable T (initially zero),
  T            // to the builtin variable T.
       ,       // Following that,
        ß      // recursively run the application again with a new input of
          Ê    // the length of
         ¢     // the current input to binary string
           É   // minus one.
            :  // If the initial check was falsy instead,
             T // we're finished, return the result which is stored in T.
```
[Try it here.](https://ethproductions.github.io/japt/?v=1.4.6&code=yT9UPaIrVCzfosrJOlQ=&input=Njc4OQ==)
[Answer]
# [Factor](https://factorcode.org/) + `math.extras`, 73 bytes
```
[ { f } swap [ [ make-bits append ] keep log2 ] until-zero reverse rest ]
```
[Try it online!](https://tio.run/##LU07DoJAFOw9xVwAAviNFpbGxsZYEYoVH0qAZX378Ec4O65gJplPMpnJVCo196fj/rBboyDWVKJSchvIP@diR0cvYWVh6d6QTsnCMIm8DedasJm0CBFhihnmWGCJFaIQYRCg62O0yNDBPpVB7FCpgrxhWRlD@oLEHZNBWV8j5xsteel9iGswPYgtObWCpK/@AyECbF3zl0f2kZakuP8C "Factor – Try It Online")
Takes an integer and returns an array of `f`s and `t`s to represent 0 and 1 bits respectively (which is the default bit array representation). `until-zero` is two bytes shorter than `dup 0 > loop`. Also, `make-bits` gives the binary representation in LSB-first order (so `4 make-bits` is `{ f f t }`), so a `reverse` is needed at the end.
```
[                              ! A quotation, input: n
  { f } swap                   ! Put the initial s="0" under n
  [ ... ] until-zero           ! Repeat until n becomes zero...
    [ make-bits append ] keep  !   Append bits of n to s, and keep n at the top
    log2                       !   Next term (floor of log 2 = bit length - 1)
  reverse rest                 ! Reverse s and remove the part representing 1
]
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 13 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
┴P&:ë▄▒ë╙G²╟ì
```
[Run and debug it](https://staxlang.xyz/#p=c150263a89dcb189d347fdc78d&i=1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A21&m=2)
A generator with a filter.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 54 bytes
```
Rest[#<>0//.a_/;a>1:>Floor@Log2@a<>a~IntegerDigits~2]&
```
[Try it online!](https://tio.run/##LYvLCsIwFET39zcKXV1tEvtSa8hCBMGFj6UUuZS0BmwLbVyJ/fUY1NWcGc60ZO@6JWsqcvXGnfVor0EhWRTN6RatSfKV3D36flCHvhGKCknTvrO60cPWNMaOkyhDd3oabdVxMJ1/z2StgjKcLhV10ws4gkBYIMQICUKKkCHkCNyv3DfhBc6YV@LkSx7TLF/@mP2DMXi7Dw "Wolfram Language (Mathematica) – Try It Online")
Returns a `StringJoin` of digits.
[Answer]
# C (MinGW), 79 bytes
Uses `itoa()` which is woefully lacking from the standard, but present on Windows systems.
The TIO link therefore contains a shoddy version of that function that only supports base 2.
```
d;f(n){int s[9]={0};d++;n>1&&f(strlen(s)-1,itoa(n,s,2));printf(--d?s:"%s0",s);}
```
[Try it online!](https://tio.run/##XVPtjpswEPwNT7GHlBwOcLHpXe5SmvYRqv5Oo4rjI7WaGISd6tIoz56uDQQDihQ8O7M7u3izaJ9lt@USfpx49gdSkUPOG3UGrqrUJ1BWDeTFsRJSNanilUgPUJ@aupKFfHJR910czpBXhYT3VBYQu9nvtIGFkXOhQITQIjIEfW7SnH8Q9@I6BlbFsd6u17ukOy8UbEDiSXM5/uNbCf6DIK7jGDIPgh1yHumjiWqDPkeAJiDwB8sNxFOyR5m3FTAHthtEbSXgUZSAFixUECDU6lqecUPNa1OoUyO0testT0pfkIu2KLfr3eZCr0keBIn4yubz0sdRHQrhSxKx0MxBhDKMCUnqBiWlH0X5N/nZm0nqhZIk19vfiuewv49LD7sbWvFRm1l1Sm8WMZp7IQiCprSJZIiBP5Pkp8CoVqFP19UZjykXvkmCvk6Zwgal@qXOdeE6CJpBC0zjTOoidHUdQ87wy8qtHqQWXBh0T@hR7xpqKB4gRnvwkwWyHny2mcjt8ZcxfuevRviQ/HWM3/lvdlGdvw@w2A5Yldlq7MiI7o2xadDyhueRN9ap@/6fX8ZWjNhwhgTUZjDzUNv26vVtPbLNWgtdOisRtVhdMjrppj1Qu1W75L15LcDPby2Y3sZ2yTh8Acn/FVXpD5eDwLIHp7eMoCQI9ILtLQFu2BPe9THQ3dvbfw "C (gcc) – Try It Online")
[Answer]
# Java 8, 77 bytes
```
n->{String r="0",b;for(;n>1;r=b+r,n=b.length()-1)b=n.toString(n,2);return r;}
```
[Try it online.](https://tio.run/##PVA9b4MwEN3zK05MWBzIJglJY5GlU4dm6RhlMMShpOSIjElVIX47NYF2ue97791d1UOF1/PXkFeqaeBdldQtAEqy2lxUruEwpgAf1pRUQO6/uU6hDRCTrtEvnGmssmUOByBIBwr33TxsUo97mMlLbXxJeyFNmgUGKc2iSlNhP30WCpalFNl6WvEJYyaNtq0hMLIf5Ih/b7PK4c80j7o8w83p9Ked4wkUm0SORE45WN3YV9Vo2AHp7/GY46kTGOMSV7jGBDe4RRGjSDAWKDjH5Wo9eo7JZvvyjPhkOe/ZE9u94Kex@hbVrY3ujthW5P8RBd4OvICi/L/C5vf0wy8)
**Explanation:**
```
n->{                    // Method with Integer parameter and String return-type
  String r="0",         //  Result-String, starting at "0"
         b;             //  Temp-String, uninitialized
  for(;n>1              //  Loop as long as `n` is larger than 1:
      ;                 //    After every iteration;
       r=b+r,           //     Prepend `b` to the result-String
       n=b.length()-1)  //     Set `n` to the length of `b` minus 1
    b=n.toString(n,2);  //   Set `b` to `n` converted to a binary-String
  return r;}            //  After the loop, return the result-String `r`
```
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 50 bytes
```
^.
$.%'*_¶$&
+`(_+)\1
${1}0
/^../}`0?_
1
^.|¶
$
0
```
[Try it online!](https://tio.run/##XYorEsIwFAD9niOF0Myk76VfFJJLME0QCAyig4NeqwfoxcJAHWZ3xU635/1x1VzY5B0lLtnoDhfFvHQW5BRR7Dnl0WN8sS/jupjd/1aN3ldz2u7Rv9cFDJKzEqhpaOnoGdCAdgRFRaib9muh64fjr2SjyAc "Retina – Try It Online") Takes input in binary, but link includes test suite with decimal to binary conversion for convenience. Explanation:
```
/^../}`
```
While the input is greater than 1, ...
```
^.
$.%'*_¶$&
```
... prepend a decremented unary copy of the length...
```
+`(_+)\1
${1}0
0?_
1
```
... and convert from unary to binary.
```
^.|¶
$
0
```
Remove the last result, join the remaining results together and append a trailing `0`.
[Answer]
# [R](https://www.r-project.org/), ~~70~~ ~~64~~ 61 bytes
```
function(N){while(N>1)F=c(N%/%2^((N=log2(N)%/%1):0)%%2,F);+F}
```
[Try it online!](https://tio.run/##bZDdCsIwDIXvfYqBFFoUTOr@VOblLvsIyhhzDuYG/uCF@OxzbkOa1Ny1X3JyTq5dUVfZ7dheijJLutOjye9V20ijXs9zVRfS7FGlSS6NWAl9kNIkdVvqnvdvVFtQQuhlqnaL9G1LSfTGUt7cg5lNtEUQKFvbDCnzyVw/SXHAMJsOKeaLI4bZdEx8fXdTjppwxxyGzPsgwe6CTo@Tov@lKXDSolf0A@Z2kBpauRyQRhwK3IBhFG9oQBztTeKOLNjNkzT8zT1@AbmN7eN3LYDuAw "R – Try It Online")
To my disappointment, a no-frills iterative implementation of the pseudocode comes-out significantly shorter than my initial [recursive approach](https://tio.run/##bZDbCsIwDIbvfYqBDFqomNQdVNwr7BHUsRODacHDlfjsc3ZDmtTeFPIlf/4/t6Huu@J@Mpe6LbKhyZrntXx05ipyZbLXW5675izyg1alMAqkakR1WPWm1SKX4TrEsZ6Pvz6Kag8yDLUyUkpXVWAwPRksA1i4RDsEgbKNy5CyiMyNkxTHDLPphGK@OGWYTW@Jr@9uylET7pnDhHm3Euwu6PV4KcYqTYGzFr1iFDO3Vsq2cjkgjWgf@AGTdLujAXGyN4t7suA2z9LwN/dUAnIb18fvWgDDBw)...
[Answer]
# [PowerShell](https://github.com/TryItOnline/TioSetup/wiki/Powershell), 77 bytes
```
param($n)while($n-1){$s=($l=[Convert]::ToString($n,2))+$s;$n=$l.Length-1}$s+0
```
[Try it online!](https://tio.run/##PYxBC4IwGIbv/oohX7EPU5xHYyF07RDVLUKEpg7WlG3lwfzta3TwPb08z8s7DpMwthdKeWj57MfGNC8KGqdeKhFKynAGyykofj8O@iOMe5Tlbbg6I3UXBrsCMQG7B81BZSehO9enbAGb5H6JQOrx7SzhBBrT2e9mrijUuIoASAwBZeslZufmeZFd7yjLEUl6IEC30JKqxpgskffMs8Kz/J8f "PowerShell – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 10 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
Î[b©#®ì®g<
```
[Try it online](https://tio.run/##yy9OTMpM/f//cF900qGVyofWHV5zaF26zf//RoYA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKS/X@DyuikQyuVD607vObQunSb/7U6/6MNdYx0jHVMdEx1zHTMdSx0DI10DM10jAx1DA0MdIxNTEG0gY6ZuYUlmGUAIQ0MYgE).
**Explanation:**
```
Î         # Push 0 and the input-integer
 [        # Start an infinite loop:
  b       #  Convert the current integer to a binary string
   ©      #  Store this binary string in variable `®` (without popping)
          #  If this binary string is equal to 1:
    #     #   Stop the infinite loop
          #   (after which the string at the top is output implicitly as result)
   ®ì     #  Prepend binary string `®` in front of the current result-string
     ®g<  #  Push the length of `®` minus 1 for the next iteration
```
[Answer]
# [Perl 5](https://www.perl.org/) (`-l060p`), 51 bytes
```
$\=($,=sprintf"%b",$_).$\,$_=-1+length$,while$_>1}{
```
[Try it online!](https://tio.run/##K0gtyjH9/18lxlZDRce2uKAoM68kTUk1SUlHJV5TTyUGSNnqGmrnpOall2So6JRnZOakqsTbGdZW//9vZPgvv6AkMz@v@L9ujoGZQQEA "Perl 5 – Try It Online")
[Answer]
# [Red](http://www.red-lang.org), ~~119~~ 115 bytes
```
func[n][o: copy"0"until[t: copy[]until[insert t n % 2 n:
to 1 n / 2 1 > n]n:(length? t)- 1 insert o t n < 1]next o]
```
[Try it online!](https://tio.run/##TZDLCsIwEEX3@YpBEHQhJrUvg@g/uA1ZlDaxhTIpMQX9@hha0ZnVuQeGy4w3XbybTmlmZbQztgq1chJaN703fDNjGEYV1qz0Ggd8Gh8gAMIWMkDJggOR0jElAVdAjXI3GnyE/gZhf0jyu@OWrQsIjeaVoo7WedO0fbKKQRoByyycET4RzgkXhEvCFeGasMgIl6RLEM/5vzcvqOe/rqo@U88pc860gskPGEBNTZeuq8Cmv@j4AQ "Red – Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 16 bytes
```
←0Ｗ⊖θ«←⮌θ≔⍘⊖Ｌθ²θ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z@gKDOvRMPKJzWtREdByUBJ05qrPCMzJ1VBwyU1uSg1NzWvJDVFo1BTU6GaixNFcVBqWWpRcSpIzpqL07G4ODM9T8MpsTg1uASoLB1Fv09qXnpJBkipjoIREBcCtdT@/28IBAaGBkBgaAChDQz@65blAAA "Charcoal – Try It Online") Link is to verbose version of code. Takes input in binary. Explanation:
```
←0
```
Output the trailing `0`.
```
Ｗ⊖θ«
```
Repeat until `N=1`.
```
←⮌θ
```
Prepend `N` to the output.
```
≔⍘⊖Ｌθ²θ
```
Replace `N` with its binary decremented length.
20 bytes for decimal input:
```
Ｎθ←0Ｗ⊖θ«←⮌⍘θ²≔⊖Ｌ⍘θ²θ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/98zr6C0xK80Nym1SKNQ05oroCgzr0TDyic1rURHQclACShUnpGZk6qg4ZKaXJSam5pXkpoCVKmpUM3FiaI4KLUstag4VcMpsTg1uAQok65RqKNgpKkJNILTsbg4Mz0PxQyf1Lz0kgwsynUUQA6p/f/f0AAM/uuW5QAA "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
Ｎθ
```
Input `N`.
```
←0
```
Output the trailing `0`.
```
Ｗ⊖θ«
```
Repeat until `N=1`.
```
←⮌⍘θ²
```
Prepend `N`'s binary representation to the output.
```
≔⊖Ｌ⍘θ²θ
```
Replace `N` with its decremented binary length.
]